fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. int n, q; 
  14. int a[N]; 
  15.  
  16. int p[N]; 
  17. map<int, int> cnt[N]; // cnt[u][c] = Số đỉnh có màu c trong thành phần liên thông (tập hợp) do u đại diện 
  18.  
  19. void initSet() {
  20. 	for (int u = 1; u <= n; u++) {
  21. 		p[u] = u;  
  22. 		cnt[u][a[u]] = 1; 
  23. 	}
  24. }
  25.  
  26. int findSet(int u) {
  27. 	if (p[u] == u) return u; 
  28. 	return p[u] = findSet(p[u]); 
  29. }
  30.  
  31. void unionSet(int u, int v) {
  32. 	u = findSet(u); 
  33. 	v = findSet(v); 
  34. 	if (u == v) return; 
  35. 	if (cnt[u].size() < cnt[v].size()) swap(u, v);  
  36. 	p[v] = u;  
  37. 	for (auto it : cnt[v]) cnt[u][it.first] += it.second;   
  38. 	cnt[v].clear();  
  39. }
  40.  
  41. int main() {
  42. 	ios::sync_with_stdio(false); 
  43. 	cin.tie(nullptr); 	
  44. 	cin >> n >> q; 
  45. 	for (int u = 1; u <= n; u++) cin >> a[u]; 
  46.  
  47. 	initSet();  
  48.  
  49. 	while (q--) {
  50. 		int type; 
  51. 		cin >> type; 
  52.  
  53. 		if (type == 1) {
  54. 			int u, v;
  55. 			cin >> u >> v; 
  56. 			unionSet(u, v); 
  57. 		}
  58. 		else {
  59. 			int u, c; 
  60. 			cin >> u >> c; 
  61. 			u = findSet(u);   
  62. 			cout << (cnt[u].count(c) ? cnt[u][c] : 0) << '\n'; 
  63. 		}
  64. 	} // O(q + nlog^2(n))
  65. }
Success #stdin #stdout 0.01s 8464KB
comments (?)
stdin
copy 
5 7
2 4 2 3 2
1 1 2
2 1 2
1 3 5
2 2 1
1 1 3
2 3 2
2 4 3
stdout
copy 
1
0
3
1
https://ideone.com/3dN5IF
language:
C++14 (gcc 8.3)
created:
305 days ago
visibility:
secret

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!