레야몬

1. 문제 함수 f:{1, 2, ..., m} -> {1, 2, ..., m} \(f_{1}(x) = f(x)\) \(f_{n+1}(x) = f(f_{n}(x))\) n, x가 주어질 때 \(f_{n}(x)\)를 계산하는 쿼리를 수행하시오 - 1 - \(m(1 \leq m \leq 200,000)\) - 2 - f(1), f(2), ..., f(m) - 3 - 쿼리의 개수 \(Q(1 \leq Q \leq 20,000)\) - Q개의 줄 - 정수 \(n, x(1 \leq n \leq 500,000, 1 \leq x \leq m)\) 주어지는 n, x마다 \(f_{n}(x)\) 출력 2. 재정의 X 3. 해결 방법 f[i][k] sparse array 4. 실수한 점, 개선할 점 input()을 안으로 뺐다..

1. 문제 N개의 중점으로 된 트리가 있다. 1~N번 매겨져 있고 간선은 1~N-1번 매겨져 있다. 아래 두 쿼리를 수행하는 프로그램을 작성하시오. 1 u v : u->v 경로 비용 출력 2 u v k : u->v 경로 정점 중 k번째 정점 출력 k는 u->v 경로에 포함된 정점 수보다 작다. - 1 - \(N(2 \leq N \leq 100,000)\) - N-1 개줄 - i번 간선 u->v와 비용 \(w(1 \leq w \leq 1,000,000)\) - N+1 - 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 쿼리 각 쿼리 결과 출력 2. 재정의 X 3. 해결 방법 트리 노드 차수 degree 설정 희소 배열 비용, 노드 메모 비용 : LCA 하면서 더하기 노드 ..

문제 N(\(2 \leq N \leq 100,000\))개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1부터 N가지 번호가 매겨져 있으며 루트는 1이다. 각 노드의 쌍 M(\(1 \leq M \leq 100,000\))개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하라. 노드의 개수 N 트리 상에 연결된 두 정점 (2~N) 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 M 정점 쌍 (N+1+M) M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 문제 재정의 스패닝 트리가 주어질 때 최소 공통 조상을 출력하라. 해결 방법 희소 배열로 부모 저장, LCA로 빠르게 탐색 실수한 점, 개선한 점 MAX_LOG의 크기를 가진 배열에 MAX_LOG번째 값..

#include #include #include #include #define FOR(i, k, N) for(int i=k; i0; i++) { if(dif%2) { //Bit 계산 Min = min(Min, min_R[a][i]); Max = max(Max, max_R[a][i]); a = PA[a][i]; } dif = dif>>1; } } if(a != b) { for(int k=MAX_TR-1; k>=0; k--) { if(PA[a][k] && PA[b][k] && PA[a][k]!=PA[b][k]) { Min = min({Min, min_R[a][k], min_R[b][k]}); Max = max({Max, max_R[a][k], max_R[b][k]}); a = PA[a][k]; b=PA[b]..