fork download
copy 
  1. // Date: 24/08/2025
  2. // Author: pppssslc
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. template<class X, class Y> void mini(X &x, const Y &y){
  8. 	x = min(x, y);
  9. }
  10.  
  11. template<class X, class Y> void maxi(X &x, const Y &y){
  12. 	x = max(x, y);
  13. }
  14.  
  15. typedef string str;
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. typedef __int128 i128;
  19. typedef double db;
  20. typedef long double ldb;
  21. typedef pair<int, int> pii;
  22. typedef pair<ll, ll> pll;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vl;
  25. typedef vector<char> vc;
  26. typedef vector<pii> vpii;
  27. typedef vector<pll> vpll;
  28. typedef vector<vector<int>> vii;
  29. typedef vector<vector<ll>> vll;
  30. typedef vector<vector<char>> vcc;
  31. typedef map<int, int> mpii;
  32. typedef map<ll, ll> mpll;
  33. typedef set<int> si;
  34. typedef set<ll> sl;
  35. typedef complex<double> cd;
  36.  
  37. #define se second
  38. #define fi first
  39. #define Rep(i, l, r, x) for(int i = l; i < (int)r; i += x)
  40. #define Repd(i, l, r, x) for(int i = l; i > (int)r; i -= x)
  41. #define For(i, l, r, x) for(int i = l; i <= (int)r; i += x)
  42. #define Ford(i, l, r, x) for(int i = l; i >= (int)r; i -= x)
  43. #define Fore(x, a) for(auto x: a)
  44. #define pb push_back
  45. #define pf push_front
  46. #define pp pop_back
  47. #define ppf pop_front
  48. #define ins insert
  49. #define era erase
  50. #define upb upper_bound
  51. #define lwb lower_bound
  52. #define all(a) a.begin(), a.end()
  53.  
  54. struct qry{
  55. 	int t, u, v;
  56. };
  57.  
  58. struct dsu{
  59. 	vi par;
  60. 	vi sz;
  61. 	stack<pair<pii, pii>> his;
  62.  
  63. 	dsu(int n){
  64. 		par.resize(n + 1);
  65. 		sz.resize(n + 1);
  66. 		For(i, 1, n, 1)
  67. 			par[i] = i, sz[i] = 1;
  68. 	}
  69.  
  70. 	int find(int i){
  71. 		while(par[i] != i) i = par[i];
  72. 		return i;
  73. 	}
  74.  
  75. 	void uni(int u, int v){
  76. 		int ru = find(u), rv = find(v);
  77. 		if(ru != rv){
  78. 			if(sz[ru] < sz[rv]) swap(ru, rv);
  79. 			his.push({{rv, par[rv]}, {ru, sz[ru]}});
  80. 			par[rv] = ru, sz[ru] += sz[rv];
  81. 		}else his.push({{-1, -1}, {-1, -1}});
  82. 	}
  83.  
  84. 	void roll(){
  85. 		auto last = his.top();
  86. 		his.pop();
  87. 		if(last.fi.fi == -1) return;
  88. 		par[last.fi.fi] = last.fi.se;
  89. 		sz[last.se.fi] = last.se.se;
  90. 	}
  91. };
  92.  
  93. const db PI = acos(-1);
  94. const ll inf = 1e18 + 1;
  95. const int mod = 1e9 + 7;
  96. const int maxn = 1e5 + 1;
  97.  
  98. int n, q;
  99. vpii st[maxn * 4];
  100. vi ans;
  101.  
  102. void upd(int id, int l, int r, int u, int v, pii e){
  103. 	if(r < u || v < l) return;
  104. 	if(u <= l && r <= v){
  105. 		st[id].pb(e);
  106. 		return;
  107. 	}
  108. 	int m = (l + r) / 2;
  109. 	upd(id * 2, l, m, u, v, e);
  110. 	upd(id * 2 + 1, m + 1, r, u, v, e);
  111. }
  112.  
  113. void get(int id, int l, int r, dsu &dsu, const vector<qry> &qries){
  114. 	Fore(e, st[id]) dsu.uni(e.fi, e.se);
  115. 	//pppssslc's code, who copies this will be a dog.
  116. 	if(l == r){ if(qries[l - 1].t == 3)
  117. 		ans.pb(dsu.find(qries[l - 1].u) == dsu.find(qries[l - 1].v));
  118. 	}else{
  119. 		int m = l + (r - l) / 2;
  120. 		get(2 * id, l, m, dsu, qries);
  121. 		get(2 * id + 1, m + 1, r, dsu, qries);
  122. 	}
  123. 	Rep(i, 0, st[id].size(), 1) dsu.roll();
  124. }
  125.  
  126. signed main(){
  127. 	ios_base::sync_with_stdio(false);
  128. 	cin.tie(nullptr); cout.tie(nullptr);
  129.  
  130. 	cin >> n >> q;
  131. 	vector<qry> qries(q);
  132. 	map<pii, stack<int>> edges;
  133.  
  134. 	Rep(i, 0, q, 1){
  135. 		cin >> qries[i].t >> qries[i].u >> qries[i].v;
  136. 		if(qries[i].u > qries[i].v) swap(qries[i].u, qries[i].v);
  137. 		if(qries[i].t == 1) edges[{qries[i].u, qries[i].v}].push(i + 1);
  138. 		else if(qries[i].t == 2){
  139. 			pii key = {qries[i].u, qries[i].v};
  140. 			if(edges.count(key) && !edges[key].empty()){
  141. 				int st = edges[key].top();
  142. 				edges[key].pop();
  143. 				upd(1, 1, q, st, i, key);
  144. 			}
  145. 		}
  146. 	}
  147.  
  148. 	for(auto &[e, t]: edges){
  149. 		while(!t.empty()){
  150. 			int st = t.top(); t.pop();
  151. 			upd(1, 1, q, st, q, e);
  152. 		}
  153. 	}
  154.  
  155. 	dsu dsu(n);
  156. 	get(1, 1, q, dsu, qries);
  157. 	Fore(x, ans) cout << x;
  158. 	return 0;
  159. }
Success #stdin #stdout 0.01s 12928KB
comments (?)
stdin
copy 
2 4
1 1 2
3 2 1
2 2 1
3 1 2
stdout
copy 
10
https://ideone.com/SU8pAW
language:
C++ (gcc 8.3)
created:
10 days 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!