比赛 2024暑假C班集训8 评测结果 AAAAAAAAAA
题目名称 玻璃球游戏 最终得分 100
用户昵称 flyfree 运行时间 3.067 s
代码语言 C++ 内存使用 14.89 MiB
提交时间 2024-07-08 11:03:30
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
int f[MAXN],p[MAXN];
int s[MAXN],x[MAXN],ans[MAXN];
int n,q,cnt;
int find(int idx,int num){
//    cout<<idx<<" ";
    if(num>=n)return -1;
    if(f[idx]==idx||f[idx]==-1)return f[idx];
    else return f[idx]=find(f[idx],num+1);
}
int main(){
    freopen("marbles.in","r",stdin);
    freopen("marbles.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        if(p[i]==0)f[i]=i;
        else f[i]=p[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>s[i]>>x[i];
        if(s[i]==2){
            f[x[i]]=x[i];
        }
    }
    for(int i=1;i<=n;i++){
        if(f[i]!=i)f[i]=find(p[i],1);
//        cout<<f[i]<<" ";
    }
    for(int i=q;i;i--){
        if(s[i]==2){
            if(find(p[x[i]],1)==x[i])f[x[i]]=-1;
            else f[x[i]]=find(p[x[i]],1);
        }else{
//            cout<<"i:"<<i<<" ";
            ans[++cnt]=find(x[i],1);
//            cout<<endl;
        }
    }
    for(int i=cnt;i;i--){
        if(ans[i]==-1)cout<<"CIKLUS\n";
        else cout<<ans[i]<<endl;
    }
    return 0;
}