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