fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-11-21 14:42:46
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-11-21 23:22:37
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name ""
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)5e5+10;
  54. int n,m,q;
  55. ii edge[N];
  56.  
  57. namespace sub2 {
  58.  
  59. 	bool approved() {
  60. 		return q <= 100 or n <= 100;
  61. 	}
  62.  
  63. 	struct DSU {
  64. 		int par[N],sz[N];
  65.  
  66. 		void init() {
  67. 			FOR(i,1,n)
  68. 			{
  69. 				par[i] = i;
  70. 				sz[i] = 1;
  71. 			}
  72. 		}
  73.  
  74. 		int acs(int u) {
  75. 			return (u == par[u] ? u : par[u] = acs(par[u]));
  76. 		}
  77.  
  78. 		bool join(int u, int v)
  79. 		{
  80. 			int x = acs(u), y = acs(v);
  81. 			if (x != y)
  82. 			{
  83. 				if (sz[x] < sz[y]) swap(x,y);
  84. 				sz[x] += sz[y];
  85. 				par[y] = x;
  86. 				return true;
  87. 			}
  88. 			return false;
  89. 		}
  90. 	} dsu;
  91.  
  92. 	void solve(void)
  93. 	{
  94. 		while (q--)
  95. 		{
  96. 			int u,v;
  97. 			cin >> u >> v;
  98. 			swap(edge[u],edge[v]);
  99. 			dsu.init();
  100. 			int tplt = n;
  101. 			FOR(i,1,m)
  102. 			{
  103. 				auto [u,v] = edge[i];
  104. 				if (dsu.join(u,v))
  105. 					tplt--;
  106. 				if (tplt == 1)
  107. 				{
  108. 					cout << i << endl;
  109. 					break;
  110. 				}
  111. 			}
  112. 		}
  113. 	}
  114.  
  115. }
  116.  
  117. namespace sub4 {
  118.  
  119. 	int key[N],id[N],visited[N],timer=0,check[N],timer2=0,tmp[N];
  120. 	vii query;
  121. 	int par[N],sz[N];
  122.  
  123. 	struct DSU {
  124. 		int n;
  125.  
  126. 		DSU() {};
  127. 		DSU(int _n):
  128. 			n(_n) {};
  129.  
  130. 		void init() {
  131. 			FOR(i,1,n)
  132. 			{
  133. 				par[i] = i;
  134. 				sz[i] = 1;
  135. 			}
  136. 		}
  137.  
  138. 		int acs(int u) {
  139. 			return (u == par[u] ? u : par[u] = acs(par[u]));
  140. 		}
  141.  
  142. 		bool join(int u, int v)
  143. 		{
  144. 			int x = acs(u), y = acs(v);
  145. 			if (x != y)
  146. 			{
  147. 				if (sz[x] < sz[y]) swap(x,y);
  148. 				sz[x] += sz[y];
  149. 				par[y] = x;
  150. 				return true;
  151. 			}
  152. 			return false;
  153. 		}
  154. 	} dsu;
  155.  
  156. 	void DnC(int dep, int nodes, vector<array<int,3>> edges, int l, int r, int best)
  157. 	{
  158. 		if (l > r) return;
  159. 		if (l == r)
  160. 		{
  161. 			key[query[l].fi] = query[l].se;
  162. 			if (l&1) return;
  163. 			sort(all(edges),[&](array<int,3> &x, array<int,3> &y) {
  164. 				return key[x[2]] < key[y[2]];
  165. 			});
  166. 			dsu = DSU(nodes);
  167. 			dsu.init();
  168. 			int mx = best;
  169. 			for (auto &e : edges)
  170. 			{
  171. 				auto [u,v,id] = e;
  172. 				if (dsu.join(u,v))
  173. 					maximize(mx,key[id]);
  174. 			}
  175. 			cout << mx << endl;
  176. 			return;
  177. 		}
  178. 		++timer;
  179. 		FOR(i,l,r) visited[query[i].fi] = timer; 
  180. 		sort(all(edges),[&](array<int,3> &x, array<int,3> &y) {
  181. 			return key[x[2]] < key[y[2]];
  182. 		});
  183. 		dsu = DSU(nodes);
  184. 		dsu.init();
  185. 		vector<array<int,3>> vec;
  186. 		for (auto &e : edges)
  187. 		{
  188. 			auto [u,v,id] = e;
  189. 			if (visited[id] == timer)
  190. 				vec.pb(e);
  191. 			else if (dsu.join(u,v))
  192. 				vec.pb(e); 
  193. 		}
  194. 		edges.swap(vec);
  195. 		dsu.init();
  196. 		for (auto &e : edges)
  197. 		{
  198. 			auto [u,v,id] = e;
  199. 			if (visited[id] == timer) dsu.join(u,v);
  200. 		}
  201. 		++timer2;
  202. 		for (auto &e : edges)
  203. 		{
  204. 			auto [u,v,id] = e;
  205. 			if (visited[id] != timer)
  206. 			{
  207. 				int pU = dsu.acs(u), pV = dsu.acs(v);
  208. 				if (pU != pV)
  209. 				{
  210. 					check[id] = timer2;
  211. 					dsu.join(pU,pV);
  212. 				}
  213. 			}
  214. 		}
  215. 		dsu.init();
  216. 		int add = best;
  217. 		for (auto &e : edges)
  218. 		{
  219. 			auto [u,v,id] = e;
  220. 			if (check[id] == timer2)
  221. 			{
  222. 				if (dsu.join(u,v))
  223. 					maximize(add,key[id]);
  224. 			}
  225. 		}
  226. 		FOR(i,1,nodes) par[i] = (!par[i] ? i : par[i]);
  227. 		FOR(i,1,nodes) 
  228. 		{
  229. 			dsu.acs(i);
  230. 			tmp[i] = 0;
  231. 		}
  232. 		int newNodes = 0;
  233. 		FOR(i,1,nodes)
  234. 		{
  235. 			int p = dsu.acs(i);
  236. 			if (!tmp[p]) tmp[p] = ++newNodes;
  237. 		}
  238. 		vector<array<int,3>> newEdges;
  239. 		for (auto &e : edges)
  240. 		{
  241. 			auto [u,v,id] = e;
  242. 			int U = tmp[dsu.acs(u)], V = tmp[dsu.acs(v)];
  243. 			if (U != V)
  244. 				newEdges.pb({U,V,id});
  245. 		}
  246. 		int mid = (l+r)>>1;
  247. 		DnC(dep+1,newNodes,newEdges,l,mid,add);
  248. 		DnC(dep+1,newNodes,newEdges,mid+1,r,add);
  249. 	}
  250.  
  251. 	void solve(void)
  252. 	{
  253. 		FOR(i,1,m) id[i] = key[i] = i;
  254. 		query.pb({0,0});
  255. 		while (q--)
  256. 		{
  257. 			int u,v;
  258. 			cin >> u >> v;
  259. 			query.pb({id[u],v});
  260. 			query.pb({id[v],u});
  261. 			swap(id[u],id[v]);
  262. 		}
  263. 		int cnt = sz(query)-1;
  264. 		vector<array<int,3>> startEdges;
  265. 		FOR(i,1,m) 
  266. 		{
  267. 			auto [u,v] = edge[i];
  268. 			startEdges.pb({u,v,i});
  269. 		}
  270. 		DnC(1,n,startEdges,1,cnt,0);
  271. 	}
  272.  
  273. }
  274.  
  275. bool M2;
  276. signed main()
  277. {
  278.     fast;
  279.     if (fopen(name".inp","r"))
  280.     {
  281.     	freopen(name".inp","r",stdin);
  282.     	freopen(name".out","w",stdout);
  283.     }
  284.     cin >> n >> m >> q;
  285.     FOR(i,1,m)
  286.    	{
  287.    		int u,v;
  288.    		cin >> u >> v;
  289.    		edge[i] = {u,v};
  290.    	}
  291.     // if (sub2::approved()) return sub2::solve(), time(), memory(), 0; 
  292.     sub4::solve();
  293.     time();
  294.     memory();
  295.     return 0;
  296. }
  297. // ██░ ██  █    ██  ███▄    █   ▄████
  298. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  299. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  300. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  301. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  302. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  303. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  304. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  305. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------------Time:6.072ms.
41.9627 MB
https://ideone.com/c2f9rO
language:
C++14 (gcc 8.3)
created:
3 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!