比赛 2024暑假C班集训8 评测结果 AAAAAAAAAA
题目名称 玻璃球游戏 最终得分 100
用户昵称 ┭┮﹏┭┮ 运行时间 0.358 s
代码语言 C++ 内存使用 17.17 MiB
提交时间 2024-07-08 10:34:11
显示代码纯文本
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 5e5+10;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


int n,m;
int f[N];

struct DSU{
    int fa[N];
    void clear(){for(int i = 1;i <= n;i++)fa[i] = i;}
    int find(int x){
        if(x == fa[x])return x;
        return fa[x] = find(fa[x]);
    }
    bool merge(int x,int y){
        x = find(x),y = find(y);
        if(x == y)return 1;
        fa[x] = y;return 0;
    }
}U;

int cnt;
int ans[N],s[N],tim[N],q[N];
vector<int>G[N];
int main(){
    freopen("marbles.in","r",stdin);
    freopen("marbles.out","w",stdout);
    n = read();
    for(int i = 1;i <= n;i++)f[i] = read();
    for(int i = 1;i <= n;i++)s[i] = i;
    //
    m = read();
    for(int i = 1;i <= m;i++){
        int op = read(),x = read();
        if(op == 1)q[i] = x;
        else tim[x] = i;
    }
    for(int i = 1;i <= n;i++)G[tim[i]].push_back(i);
    U.clear();
    for(int i = 0;i < G[0].size();i++)
        if(f[G[0][i]] && U.merge(G[0][i],f[G[0][i]]))s[U.find(G[0][i])] = -1;
    for(int i = m;i >= 1;i--){
        if(q[i])ans[i] = s[U.find(q[i])];
        for(int j = 0;j < G[i].size();j++)
            if(f[G[i][j]] && U.merge(G[i][j],f[G[i][j]]))s[U.find(G[i][j])] = -1;
    }
    for(int i = 1;i <= m;i++)
        if(ans[i] != 0){
            if(ans[i] == -1)printf("CIKLUS\n");
            else printf("%d\n",ans[i]);
        }
    
    return 0;
    
}