比赛 |
2024暑假C班集训8 |
评测结果 |
AAAAAAAAAA |
题目名称 |
玻璃球游戏 |
最终得分 |
100 |
用户昵称 |
liuyiche |
运行时间 |
0.538 s |
代码语言 |
C++ |
内存使用 |
7.31 MiB |
提交时间 |
2024-07-08 10:14:09 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n, q;
int fa[300010];
bool vis[300010];
int d[300010];
bool pd[300010];
int ans[300010];
struct qus
{
int op;
int x;
};
qus v[300010];
inline int get(int step)
{
if(fa[step] == -1)
return -1;
if(vis[step] == 1)
return fa[step] = -1;
if (fa[step] == step)
return step;
vis[step] = 1;
fa[step] = get(fa[step]);
vis[step] = 0;
return fa[step];
}
inline void merge(int x, int y)
{
int xroot = get(x);
vis[x] = 1;
fa[xroot] = get(y);
vis[x] = 0;
}
int main()
{
freopen("marbles.in", "r", stdin);
freopen("marbles.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
fa[i] = i;
for(int i = 1; i <= n; ++i)
cin >> d[i];
cin >> q;
for(int i = 1; i <= q; ++i)
{
cin >> v[i].op >> v[i].x;
if(v[i].op == 2) pd[v[i].x] = 1;
}
for(int i = 1; i <= n; ++i)
if(d[i] != 0 && pd[i] == 0)
merge(i,d[i]);
for(int i = q; i > 0; --i)
{
if(v[i].op == 1)
ans[i] = get(v[i].x);
else
if(d[v[i].x] != 0)
merge(v[i].x,d[v[i].x]);
}
for(int i = 1; i <= q; ++i)
if(v[i].op == 1)
{
if(ans[i] == -1)
cout << "CIKLUS" << '\n';
else cout << ans[i] << '\n';
}
return 0;
}