Submission #13110007

---

Source Code Expand

//Author rahuliitkgp
/*A thing of beauty is a joy forever,
Its loveliness increases,
it will never pass into nothingness.*/
//Men at Work :)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

void cpp() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int main() {
    cpp();
    ll n, k;
    cin>>n>>k;
    vector<ll> v(n+1);
    for(ll i=0; i<n; i++) cin>>v[i+1]; //one based indexing

    //floyd warshall cycle detection algorithm starts here to find start of cycle
    ll l = v[1];
    ll r = v[v[1]];
    while(l!=r){
        l = v[l];
        r = v[v[r]];
    }
    l = 1;
    while(l!=r){
        l=v[l];
        r=v[r];
    }
    //floyd warshall cycle detection algorithm ends here to find start of cycle

    ll cycleStar = l;  //starting point of cycle
    ll cnt = 0;  //number of elements before the starting point of cycle
    l = 1;
    while(l!=cycleStar){
        cnt++;
        l = v[l];
    }

    ll eleBefore = cnt;  //number of elements before the starting point of cycle
    ll lenn = 1;   //length of cycle(num of elements in it)
    l = cycleStar;
    while(v[l]!=cycleStar){
        l=v[l];
        lenn++;
    }
    
    // moving king to the starting point of cycle if k becomes zero in between we are breaking early and printing the answer
    l = 1;
    while((eleBefore!=0)&&(k)){
        l=v[l];
        eleBefore--;
        k--;
    }
    
    // printing answer if k becomes zero in between reaching the start of cycle
    if(k==0){
        cout<<l<<endl;
        return 0;
    }
    
    // now we are at start of cycle we can reduce k to k%lenn because if k> len king will move in cycle
    k=k%lenn;
    
    //now k is less than length of cycle
    //just move king k steps forward
    while(k){
        l=v[l];
        k--;
    }
    //print ans
    cout<<l<<endl;
    return 0;
}

Submission Info

Judge Result