코딩생활

https://jungol.co.kr/problem/8397?cursor=MTIsMiw0아이디어간선의 가중치가 2x의 꼴이므로 경로의 가중치의 합이 최소가 되기 위해서는 경로상에 존재하는 최대의 x값을 최소화해야합니다. 이는 x값이 증가하는 순서대로 관찰하며 스패닝 트리를 만들었을 때 그 트리상의 경로와 같아지게 됩니다. 그러므로 x가 증가하는 순서대로 스패닝 트리를 만들고, 그 스패닝 트리에서 LCA를 통하여 경로상의 정점의 개수를 세어주면 됩니다.소스코드#include #include #include #define ll long longusing namespace std;ll par[202020]={0};ll find(ll x){ if (x==par[x]) return x; return p..

카테고리 없음 2026. 4. 27. 16:00

https://jungol.co.kr/problem/3600?cursor=MTIsMiww아이디어오일러 투어 테크닉을 통해서 모든 노드마다 방문 번호를 붙여줍시다. 그러면 어떠한 노드 x를 루트로 하는 서브트리에 존재하는 모든 노드들을 직선상의 하나의 구간으로 표현할 수 있게 됩니다. 그러면 세그먼트 트리를 이용해서 문제를 해결해줄 수 있게 됩니다.소스코드#include #include #include #define ll long longusing namespace std;ll tree[1212121]={0};ll Sum(ll s,ll e,ll node,ll l,ll r){ if (e Graph[303030];ll In[303030]={0},Out[303030]={0},cnt=0;void DFS(ll..

PS,CP 2026. 4. 27. 09:00

https://jungol.co.kr/problem/6276?cursor=MTIsMCwy아이디어Exchange Argument를 사용하면 b/a의 값이 증가하는 순서대로 배열하는것이 최적임을 알 수 있습니다. 하지만 이때 a와 b의 값이 0일때에는 따로 처리를 해주어야합니다.소스코드#include #include #include #define ll long longusing namespace std;bool cmp(pair A,pair B){ if (A.first==0 && A.second==0) return false; if (B.first==0 && B.second==0) return true; if (A.first || B.first) return A.first*B.second>..

PS,CP 2026. 4. 26. 16:00

https://jungol.co.kr/problem/8356?cursor=MTIsMSw2아이디어세그먼트 트리를 구조체로 만들어봅시다. 각 구간에서 콜라의 최댓값, 치킨의 최댓값, 그 구간에서 두개를 고를때의 최댓값을 저장해봅시다. 그리고 왼쪽과 오른쪽을 병합할 때 그 값들을 갱신시켜주면 됩니다. 그러면 O(log N)에 변경과 최댓값 구하기 쿼리를 다 처리할 수 있습니다.소스코드#include #include #define ll long longusing namespace std;struct Tree{ ll ColaMax=-1e18,ChickenMax=-1e18,Ans=-1e18;};Tree operator+(Tree A,Tree B){ Tree res; res.ColaMax=max(A...

PS,CP 2026. 4. 26. 09:00

https://jungol.co.kr/problem/4973?cursor=MTIsMSw0아이디어어떠한 x에 대하여 x가 Ai이상 Bi이하인 i의 개수가 x이상이여야합니다. 그러기 위해서는 초기에 arr[1]=-1, arr[2]=-2, ... arr[N]=-N으로 저장한 다음, Ai, Bi가 주어지면 [Ai,Bi]에 1을 더해주는 쿼리를 느리게 갱신되는 세그먼트 트리로 처리해준 다음, arr배열에서 0이상의 수가 존재하는 가장 큰 인덱스를 찾아주면 됩니다.소스코드#include #define ll long longusing namespace std;ll tree[2020202]={0},lazy[2020202]={0};void pp(ll s,ll e,ll node){ tree[node]+=lazy[no..

PS,CP 2026. 4. 25. 16:00

https://jungol.co.kr/problem/8082?cursor=MTIsMSww아이디어느리게 갱신되는 세그먼트 트리의 기본 문제입니다. lazy[node]를 node에 저장된 갱신값이라고 정의하며, pp(s,e,node)를 node에 저장된 갱신값을 tree값으로 옮기고 자식에게 갱신값을 물려주는 함수로 정의합니다.소스코드#include #define ll long longusing namespace std;ll tree[4040404]={0},lazy[4040404]={0};void pp(ll s,ll e,ll node){ tree[node]+=lazy[node]*(e-s+1); if (s!=e) { lazy[node*2]+=lazy[node]; laz..

PS,CP 2026. 4. 25. 09:00

https://jungol.co.kr/problem/5686?cursor=MTMsMSw1아이디어0이상 2M미만의 수를 정점으로 하는 그래프를 생각해봅시다. 이때 i와 j를 잇는 간선이 있다는것은 i와 j사이의 해밍 거리가 1이라는것을 의미합니다. 그러면 등장하는 모든 x에 대하여 가장 멀리 떨어진 점을 찾아주면 됩니다. 이는 2M-1 xor x와 가장 가까운 거리에 있는 점을 의미하므로, 모든 x에 대하여 2M-1 xor x들을 잡고, 이것들을 기준으로 멀티소스 BFS를 사용해주면 각 점마다 가장 가까운 점까지의 거리를 구할 수 있습니다.소스코드#include #include #define ll long longusing namespace std;bool visit[1050101]={0};int dis[..

PS,CP 2026. 4. 24. 16:00

https://jungol.co.kr/problem/1246?cursor=MTMsNCwy아이디어준식이 P 이상일 수 있는지의 여부를 판단해봅시다. 그러기 위해서는 ai-P*bi의 값중 가장 큰 N-K개의 합이 0이상이여야합니다. 그러므로 0이상 1이하의 P에 대해서 매개변수탐색을 진행해주면 됩니다소스코드#include #include #include #define ll long longusing namespace std;bool Able(vector A,vector B,double P,ll K){ ll N=A.size(); vector v; for (ll i=0;i()); double sum=0; for (ll i=0;i=0;}int main(){ ios_base::..

PS,CP 2026. 4. 24. 09:00