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