백준 문제풀이

BOJ 3117.cpp

#include <bits/stdc++.h>
using namespace std;
// LCA 에서 쓰는 방식
const int MAX = 100001;

int N, K, M, student[MAX];
int video[MAX][32];
int MakeAns(int curr, int Remain){
	int idx = 0;
	while(Remain){
		if(Remain%2) curr = video[curr][idx];
		idx++;
		Remain/=2;		
	}
	return curr;
}
int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
cin >> N >> K >> M;
for (int i = 1; i <= N; ++i)
	cin >> student[i];
memset(video,-1,sizeof(video));
for (int i = 1; i <= K; ++i) cin >> video[i][0];
// video[i][j] = i동영상 에서 2^j 번만큼 갔을 때 동영상
for (int j = 0; j < 31; ++j){
	for (int i = 1; i <= K; ++i){
		int parent = video[i][j];		
		video[i][j+1] = video[parent][j];
	}
}
for (int i = 1; i <= N; ++i) 
	cout << MakeAns(student[i],M-1) << ' ';
return 0;
}