Submission #7997170

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <set>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int visit[100005];
int mod[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a;
    string s;
    cin >> n >> a >> s;
    --a;
    vector<int> b(n);
    for(int i = 0; i < n; ++i){
        cin >> b[i];
        --b[i];
    }
    
    int now = a;
    ++visit[a];
    vector<int> tmp;
    tmp.push_back(now);
    for(;;){
        now = b[now];
        if(visit[now] == 2)     break;
        if(visit[now] == 0){
            ++visit[now];
            tmp.push_back(now);
        }
        else{
            ++visit[now];
        }
    }

    int st;     // 閉路のスタート地点のtmpのindex
    for(int i = 0; i < (int)tmp.size(); ++i){
        if(visit[tmp[i]] == 2){
            st = i;
            break;
        }
    }
    int cnt = 0;    // 閉路に含まれる頂点数
    for(int i = 0; i < n; ++i){
        if(visit[i] == 2){
            ++cnt;
        }
    }
    int cnt2 = (int)tmp.size() - cnt;    // 閉路に含まれない頂点数
    int len = (int)s.length();

    int digit1 = (int)(to_string(cnt).length());
    int digit2 = (int)(to_string(cnt2).length());
    if(len <= digit2){
        int num = 0;
        int mul = 1;
        for(int i = len - 1; i >= 0; --i){
            num += (s[i] - '0') * mul;
            mul *= 10;
        }
        if(num < cnt2){     // 閉路に入っていない場合
            cout << ++tmp[num] << endl;
            return 0;
        }
        num -= cnt2;
        string t = to_string(num);
        for(int i = 0; i < len; ++i){
            if(i >= len)    break;
            
            if(i >= (int)t.length()){
                s[len - 1 - i] = '0';
            }
            else{
                s[len - 1 - i] = t[len - 1 - i];
            }
        }
        for(int i = 0; i < len; ++i){
            mod[i+1] = (mod[i] * 10 % cnt + (s[i] - '0')) % cnt;
        }
        cout << ++tmp[st + mod[len]] << endl;
        return 0;
    }

    int num = 0;
    int mul = 1;
    for(int i = len - 1; i >= len - digit2; --i){
        num += (s[i] - '0') * mul;
        mul *= 10;
    }
    // 操作回数の補正(この補正で閉路以外の頂点を辿ったことにする)
    if(num >= cnt2){
        num -= cnt2;
        string t = to_string(num);
        int len2 = (int)t.length();
        for(int i = 0; i < digit2; ++i){
            if(i >= len)    break;
            if(i >= len2){
                s[len - 1 - i] = '0';
            }
            else{
                s[len - 1 - i] = t[len2 - 1 - i];
            }
        }
    }
    else{
        num += (s[len - digit2 - 1] - '0') * mul;
        num -= cnt2;
        string t = to_string(num);
        int len2 = (int)t.length();
        for(int i = 0; i < digit2 + 1; ++i){
            if(i >= len)    break;
            if(i >= len2){
                s[len - 1 - i] = '0';
            }
            else{
                s[len - 1 - i] = t[len2 - 1 - i];
            }
        }
    }
    for(int i = 0; i < len; ++i){
        mod[i+1] = (mod[i] * 10 % cnt + (s[i] - '0')) % cnt;
    }
    cout << ++tmp[st + mod[len]] << endl;
}

Submission Info

Judge Result