[백준] 17435 - 합성 함수와 쿼리

https://www.acmicpc.net/problem/17435

17435번: 합성함수와 쿼리

 

x -> f(x)가 되는 그래프를 그려보면, 여러 개의 그래프가 그려진다.

합성 함수이므로 사이클이 생기게 되고, 그에 맞게 답을 내면 된다.

 

하지만 쿼리의 n 만큼 반복하게 되면 TLE를 받을것이다. 따라서 LCA를 구했던 것처럼 sparse table을 이용해 log 시간 복잡도에 해결할 것이다.

 

dp[i][j] = f_(2^j) (i)로 정의하였다.

수식이 약간 이상하지만, i정점의 2^j번째 부모라고 생각하면 된다.

 

#include <iostream>
#include <cmath>
using namespace std;

int dp[200001][21];

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n; cin >> n;

	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		dp[i][0] = a;
	}

	for (int j = 1; j <= 20; j++) {
		for (int i = 1; i <= n; i++) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}

	int q; cin >> q;

	for (int i = 0; i < q; i++) {
		
		int a, b; cin >> a >> b;

		for (int i = 20; i >= 0; i--) {
			int k = pow(2, i);
			if (a >= k) {
				a -= k;
				b = dp[b][i];
			}
		}

		cout << b << '\n';
	}
}