YouTube - 3117

//3117 - youtube
 
#include <iostream>
using namespace std;
 
int N, K, M;
int arr[100001][31];
int student[100001];
 
void init()
{
    cin >> N >> K >> M;
    for (int i = 0; i < N; ++i)
        cin >> student[i];
    for (int i = 1; i <= K; ++i)
        cin >> arr[i][0];
 
    for (int j = 1; j < 31; ++j)
        for (int i = 1; i <= K; ++i)
            arr[i][j] = arr[arr[i][j - 1]][j - 1];
}
 
int Ldigit(int u)
{
    int ret = 0;
    while (u % 2 == 0)
    {
        u /= 2;
        ++ret;
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    for (int i = 0; i < N; ++i)
    {
        int u = student[i];
        int v = M-1;
        while (v)
        {
            u = arr[u][Ldigit(v)];
            v &= (v - 1);
        }
        cout << u << " ";
    }
}

 

 

 

 

 

 

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

3117번: YouTube

 

 

 

 

 

 

YouTube

희소테이블을 이용해 해결했습니다!

희소테이블을 초기화할때는 반드시 이동하는 횟수가 증가하도록 초기화 해주어야 합니다!!

즉 제 코드에선 2차원 배열의 열이 이동하는 횟수를 담당하고 있는데

초기화를 위해서 이중반복문이 한 열의 행들을 모두 채우고 그다음 열로 넘어가게 초기화를 해주어야 합니다!