比赛 2024暑假C班集训8 评测结果 AAAAAAAAAA
题目名称 玻璃球游戏 最终得分 100
用户昵称 小金 运行时间 0.611 s
代码语言 C++ 内存使用 7.56 MiB
提交时间 2024-07-08 11:06:44
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
int n,q,a[300010],fa[300010],ans[300010],c[300010][2],b[300010],s,s1;
int find(int x)
{
    if(s>2*n) return -1;
    s++;
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
int main()
{
    freopen("marbles.in","r",stdin);
    freopen("marbles.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&c[i][0],&c[i][1]);
        if(c[i][0]==2)
        {
            b[c[i][1]]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==1||a[i]==0)
        {
            fa[i]=i; 
        }
        else
        {
            fa[i]=a[i]; 
        }
    }
    for(int i=q;i>=1;i--)
    {
        s=0;
        if(c[i][0]==1)
        {
            s1++;
            ans[s1]=find(c[i][1]); 
        }
        else
        {
            if(a[c[i][1]]!=0) fa[c[i][1]]=a[c[i][1]];
        } 
    }
    for(int i=s1;i>=1;i--)
    {
        if(ans[i]==-1||ans[i]==0) printf("CIKLUS\n");
        else printf("%d\n",ans[i]);
    }
    return 0;
}