比赛 2024暑假C班集训8 评测结果 AAAAAAAAAA
题目名称 玻璃球游戏 最终得分 100
用户昵称 darkMoon 运行时间 0.557 s
代码语言 C++ 内存使用 11.68 MiB
提交时间 2024-07-08 09:33:47
显示代码纯文本
#include<bits/stdc++.h> 
#define int long long
using namespace std;
//#define fin cin
//#define fout cout
ifstream fin("marbles.in");
ofstream fout("marbles.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 3e5 + 5;
int n = mread(), to[N], q, op[N], x[N], fa[N], e[N], p[N];
int findfa(int x){
    if(x == fa[x])
    return x;
    return fa[x] = findfa(fa[x]);
}
void add(int x, int y){
    //from x to y
    int t1 = findfa(x), t2 = findfa(y);
    if(t1 == t2){
        p[t1] = 1; 
    }
    fa[t1] = t2;
    return;
}
signed main(){
    for(int i = 1; i <= n; i ++)
    fa[i] = i;
    for(int i = 1; i <= n; i ++){
        to[i] = mread();
    }
    q = mread();
    for(int i = 1; i <= q; i ++){
        op[i] = mread();
        x[i] = mread(); 
        if(op[i] == 2)
        e[x[i]] = 1;
    }
    for(int i = 1; i <= n; i ++){
        if(e[i] == 0){
            if(to[i])
            add(i, to[i]);
        }
    }
    stack<int> ans;
    for(int i = q; i >= 1; i --){
        if(op[i] == 2){
            if(to[x[i]])
            add(x[i], to[x[i]]);
        }
        else{
            int tmp = findfa(x[i]);
            if(p[tmp] == 1){
                ans.push(-1);
            }
            else{
                ans.push(tmp);
            }
        }
    }
    while(ans.size()){
        if(ans.top() == -1){
            fout << "CIKLUS\n";
        }
        else{
            fout << ans.top() << "\n";
        }
        ans.pop();
    }
    return 0;
}