比赛 |
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;
}