fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. #define ff first
  7. #define ss second
  8. #define rep(i,n) for(int i=0;i<n;i++)
  9. #define repn(i,a,b) for(int i=a; i<b;i++)
  10. #define opn printf("\n")
  11.  
  12.  
  13. typedef pair<int,int> pi;
  14. typedef vector<pi> vp;
  15. typedef vector<vp> vvp;
  16. typedef vector<int> vi;
  17. typedef unsigned long long int ull;
  18. typedef long long int ll;
  19. typedef vector<ll> vl;
  20. typedef vector< vi > vvi;
  21. typedef priority_queue<int> pq;
  22. typedef priority_queue<int, vi , greater<int> >minpq;
  23. typedef priority_queue<pi,vp,greater<pi> > mpq;
  24.  
  25. int a[100002];
  26.  
  27. int P[100002];
  28. int R[100002];
  29.  
  30. map<int,int>M;
  31.  
  32. int val[100002];
  33.  
  34. void init(int n){
  35. 	for(int i=0 ; i<n ;i++){
  36. 		P[i] = i;
  37. 		R[i] = 0 ;
  38. 	}
  39. }
  40.  
  41. int FindParent(int x){
  42. 	while(x != P[x]){
  43. 		x = P[x];
  44. 	}
  45. 	return x;
  46. }
  47.  
  48. int mergeSets(int x, int y){
  49. 	int px = FindParent(x);
  50. 	int py = FindParent(y);
  51. 	if( px == py){
  52. 		return px;
  53. 	}
  54.  
  55. 	if(R[px] > R[py]){
  56. 		P[py] = px;
  57. 		return px;
  58. 	}
  59. 	else{
  60. 		P[px] = py;
  61. 		if(R[px] == R[py]){
  62. 			R[py]++;
  63. 		}
  64. 		return py;
  65. 	}
  66.  
  67. }
  68.  
  69. void calc(int n){
  70. 	init(n);
  71. 	for(int i=0; i<n; i++){
  72. 		auto it = M.find(a[i]);
  73. 		if(it == M.end()){
  74. 			M.insert({a[i],i});
  75. 			val[i] = a[i]; 
  76. 		}
  77. 		else{
  78. 			mergeSets(i,it->ss);
  79. 		}
  80. 	}
  81. }
  82.  
  83. int main(){
  84. 	//ios_base::sync_with_stdio(false);cin.tie(NULL);
  85. 	int t;
  86. 	cin>>t;
  87. 	rep(j,t){
  88. 		M.clear();
  89. 		cout<<"Case "<<j+1<<":";opn;
  90. 		int n,q;
  91. 		cin>>n>>q;
  92. 		rep(i,n+1){
  93. 			P[i] = 0;
  94. 			R[i] = 0;
  95. 			val[i] = 0;
  96. 		}
  97. 		rep(i,n) cin>>a[i];
  98. 		calc(n);
  99. 		rep(i,q){
  100.  
  101. 			int type;
  102. 			cin>>type;
  103. 			if(type==1){
  104. 				int x,y;
  105. 				cin>>x>>y;
  106. 				if(x==y)
  107. 					continue;
  108. 				auto it1 = M.find(x);
  109. 				auto it2 = M.find(y);
  110.  
  111. 				if(it1 != M.end()){
  112. 					if(it2 != M.end()){
  113. 						int px = mergeSets(it1->ss,it2->ss);
  114. 						M.erase(it1);
  115. 						M.erase(it2);
  116. 						M.insert({y,px});
  117. 						val[px] = y;
  118. 					}
  119. 					else{
  120. 						M.insert({y,it1->ss});
  121. 						val[it1->ss] = y; 
  122. 						M.erase(it1);
  123. 					}
  124. 				} 
  125. 			}
  126. 			else{
  127. 				int idx;
  128. 				cin>>idx;
  129. 				int re = FindParent(idx-1);
  130. 				cout<<val[re];opn;
  131. 			}
  132. 		}
  133. 	}
  134.  
  135. }
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
1
5 4
1 2 3 4 5
1 1 3
2 1
1 3 5
2 1
stdout
copy 
Case 1:
3
5
https://ideone.com/sifJ4v
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!