比赛 2024暑假C班集训8 评测结果 AAAAAAAAAA
题目名称 玻璃球游戏 最终得分 100
用户昵称 小金 运行时间 0.611 s
代码语言 C++ 内存使用 7.56 MiB
提交时间 2024-07-08 11:06:44
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int n,q,a[300010],fa[300010],ans[300010],c[300010][2],b[300010],s,s1;
  5. int find(int x)
  6. {
  7. if(s>2*n) return -1;
  8. s++;
  9. if(fa[x]==x) return x;
  10. else return fa[x]=find(fa[x]);
  11. }
  12. int main()
  13. {
  14. freopen("marbles.in","r",stdin);
  15. freopen("marbles.out","w",stdout);
  16. scanf("%d",&n);
  17. for(int i=1;i<=n;i++)
  18. {
  19. scanf("%d",&a[i]);
  20. }
  21. scanf("%d",&q);
  22. for(int i=1;i<=q;i++)
  23. {
  24. scanf("%d%d",&c[i][0],&c[i][1]);
  25. if(c[i][0]==2)
  26. {
  27. b[c[i][1]]=1;
  28. }
  29. }
  30. for(int i=1;i<=n;i++)
  31. {
  32. if(b[i]==1||a[i]==0)
  33. {
  34. fa[i]=i;
  35. }
  36. else
  37. {
  38. fa[i]=a[i];
  39. }
  40. }
  41. for(int i=q;i>=1;i--)
  42. {
  43. s=0;
  44. if(c[i][0]==1)
  45. {
  46. s1++;
  47. ans[s1]=find(c[i][1]);
  48. }
  49. else
  50. {
  51. if(a[c[i][1]]!=0) fa[c[i][1]]=a[c[i][1]];
  52. }
  53. }
  54. for(int i=s1;i>=1;i--)
  55. {
  56. if(ans[i]==-1||ans[i]==0) printf("CIKLUS\n");
  57. else printf("%d\n",ans[i]);
  58. }
  59. return 0;
  60. }