Submission #536667

---

Source Code Expand

#include <iostream>
#include <cstring>

int N, a;
int b[100000];
int ts[100000];
std::string K;

int main(){
    std::cin >> N >> a;
    --a;
    
    std::cin >> K;
    
    for(int i=0;i<N;i++){
        std::cin >> b[i];
        --b[i];
    }

    if(K.size() < 7){
        int k = std::stoi(K);
        for(int i=0;i<k;i++){
            a = b[a];
        }

        std::cout << a+1 << std::endl;
        return 0;
    }
    

    memset(ts, -1, sizeof(ts));

    int t = 0;
    for(;ts[a]==-1;){
        ts[a] = t;
        ++t;
        // printf("%d -> %d\n", a, b[a]);
        a = b[a];
    }

    // for(int i=0;i<N;i++){
    //     printf("%d\n", ts[i]);
    // }
    
    int mod = t - ts[a], k = 0;

    // printf("%d, %d\n", mod, k);
    
    for(char& c : K){
        k = (k * 10 + c - '0') % mod;
    }

    k = ((k - ts[a]) % mod + mod) % mod;

    for(;k>0;k--){
        a = b[a];
    }

    std::cout << a+1 << std::endl;
}

Submission Info

Judge Result