Submission #7996053

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}

const char EOL = '\n';
const int MOD = 1000000007;
const int INF = 1000000001;

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

int calc_mod(string s, int d) {
    int r = 0;
    REP(i, s.size()) r = (r * 10 + (s[i] - '0')) % d;
    return r;
}

void solve() {
    int n, a;
    string s;
    cin >> n >> a >> s;
    a--;
    vector<int> b(n);
    REP(i, n) {
        cin >> b[i];
        b[i]--;
    }

    auto full = [&](int start, int k) {
        int c = start;
        REP(i, k) c = b[c];
        return c;
    };

    auto cycle = [&](string k) {
        vector<int> p(n, -1);
        p[a] = 0;
        int c = a;
        int l;
        REP1(i, 2 * n) {
            c = b[c];
            if (p[c] != -1) {
                l = i - p[c];
                return full(c, (calc_mod(k, l) - p[c] + l) % l);
            }
            p[c] = i;
        }
        
    };

    int ans;
    if (s.size() < 6 || s == "100000") {
        int k = stoi(s);
        if (n * 2 >= k) {
            ans = full(a, k);
        } else {
            ans = cycle(s);
        }
    } else {
        ans = cycle(s);
    }

    cout << ans + 1 << EOL;
}

Submission Info

Judge Result