Submission #72031170

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,q,a[N],vis[N],bel[N],pos[N],len[N],cnt;
int cyc_sum[N];
vector<int>v[N];
void dfs(int u){
    if(vis[u]){
        if(!bel[u]){
            cnt++;
            int x=u;
            int sz=0;
            vector<int>tmp;
            do{
                tmp.push_back(x);
                bel[x]=cnt;
                pos[x]=sz++;
                x=a[x];
            }while(x!=u);
            len[cnt]=sz;
            v[cnt]=tmp;
            
            for(auto val:tmp)cyc_sum[cnt]+=val;
        }
        return;
    }
    vis[u]=1;
    dfs(a[u]);
    if(!bel[u]){
        bel[u]=bel[a[u]];
        pos[u]=pos[a[u]]-1;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
    for(int i=1;i<=q;i++){
        int T,B;
        cin>>T>>B;
        int cur=B,ans=0,steps=0;
        while(pos[cur]<0 && steps<T){
            ans+=cur;
            cur=a[cur];
            steps++;
        }
        T-=steps;
        if(T>0){
            int c=bel[cur];
            int p=pos[cur];
            int l=len[c];
            int full_cycles=T/l;
            ans+=full_cycles*cyc_sum[c];
            int rem=T%l;
            for(int j=0;j<rem;j++){
                int person=v[c][(p+j)%l];
                ans+=person;
            }
        }
        
        cout<<ans<<'\n';
    }
    return 0;
}

Submission Info

Judge Result