fork download 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890123456789LL
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. typedef long long cat;
  35.  
  36. #ifdef DONLINE_JUDGE
  37. 	// palindromic tree is better than splay tree!
  38. 	#define lld I64d
  39. #endif
  40.  
  41. bool DFS_mxedge(int R, int par, auto &G, int goal, int &g) {
  42. 	// is it above the goal?
  43. 	if(R == goal) return 1;
  44. 	ALL_THE(G[R],it) if(it->ff != par)
  45. 		if(DFS_mxedge(it->ff,R,G,goal,g)) {
  46. 			g =max(g,it->ss);
  47. 			return 1;
  48. 		}
  49. 	return 0;
  50. }
  51.  
  52. void DFS_comps(int R, int par, auto &G, auto &inCc, auto &C) {
  53. 	inCc[R] =1;
  54. 	C.push_back(R);
  55. 	ALL_THE(G[R],it) if(it->ff != par)
  56. 		DFS_comps(it->ff,R,G,inCc,C);
  57. }
  58.  
  59. void DFS(int R, int par, auto &G, auto &V, auto &Rt) {
  60. 	ALL_THE(G[R],it) if(it->ff != par) {
  61. 		DFS(it->ff,R,G,V,Rt);
  62. 		Rt[it->ss] =min(Rt[it->ss],V[it->ff]);
  63. 		V[R] =min(V[R],V[it->ff]);
  64. 	}
  65. }
  66.  
  67. int main() {
  68. 	cin.sync_with_stdio(0);
  69. 	cin.tie(0);
  70. 	cout << fixed << setprecision(10);
  71. 	int T, N =10010;
  72. 	cin >> T;
  73. 	while(T--) {
  74. 		int M;
  75. 		cin >> M;
  76. 		vector< pair<int,int> > E(M);
  77. 		for(int i =0; i < M; i++) {
  78. 			cin >> E[i].ff >> E[i].ss;
  79. 			E[i].ff--, E[i].ss--;
  80. 		}
  81. 		vector<int> ans(M,0), R(M,M);
  82.  
  83. 		vector<bool> inT(M,0);
  84. 		vector< vector<int> > comp(N);
  85. 		vector<int> inC(N);
  86. 		for(int i =0; i < N; i++) {
  87. 			inC[i] =i;
  88. 			comp[i].push_back(i);
  89. 		}
  90. 		vector< vector< pair<int,int> > > G(N);
  91.  
  92. 		vector<bool> inC1(N,0),inC2(N,0);
  93. 		vector<int> V(N), C1, C2;
  94. 		for(int L =M-1; L >= 0; L--) {
  95. 			int u =E[L].ff, v =E[L].ss;
  96. 			inT[L] =1;
  97.  
  98. 			if(inC[u] != inC[v]) {
  99. 				// merge components
  100. 				u =inC[u], v =inC[v];
  101. 				if(comp[u].size() < comp[v].size()) swap(u,v);
  102. 				ALL_THE(comp[v],it) {
  103. 					comp[u].push_back(*it);
  104. 					inC[*it] =u;
  105. 				}
  106. 				u =E[L].ff, v =E[L].ss;
  107. 			}
  108. 			else {
  109. 				// remove an edge from T
  110. 				int g =0;
  111. 				DFS_mxedge(u,u,G,v,g);
  112. 				inT[g] =0;
  113. 				int a =E[g].ff, b =E[g].ss;
  114. 				for(int i =0; i < (int)G[a].size(); i++) if(G[a][i].ss == g) {
  115. 					swap(G[a][i],G[a].back());
  116. 					G[a].pop_back();
  117. 					break;
  118. 				}
  119. 				for(int i =0; i < (int)G[b].size(); i++) if(G[b][i].ss == g) {
  120. 					swap(G[b][i],G[b].back());
  121. 					G[b].pop_back();
  122. 					break;
  123. 				}
  124. 			}
  125. 			DFS_comps(u,u,G,inC1,C1);
  126. 			DFS_comps(v,v,G,inC2,C2);
  127. 			G[u].push_back(make_pair(v,L));
  128. 			G[v].push_back(make_pair(u,L));
  129.  
  130. 			for(int i =L; i < M; i++) V[E[i].ff] =V[E[i].ss] =M;
  131. 			for(int i =L+1; i < M; i++) if(!inT[i]) {
  132. 				R[i] =i;
  133. 				if(inC2[E[i].ff] && inC1[E[i].ss]) swap(E[i].ff,E[i].ss);
  134. 				if(inC1[E[i].ff] && inC2[E[i].ss]) {
  135. 					R[L] =min(R[L],i);
  136. 					V[E[i].ff] =min(V[E[i].ff],i);
  137. 					V[E[i].ss] =min(V[E[i].ss],i);
  138. 				}
  139. 			}
  140.  
  141. 			DFS(u,v,G,V,R);
  142. 			DFS(v,u,G,V,R);
  143.  
  144. 			ALL_THE(C1,it) inC1[*it] =0;
  145. 			ALL_THE(C2,it) inC2[*it] =0;
  146. 			C1.clear();
  147. 			C2.clear();
  148.  
  149. 			for(int i =L; i < M; i++) ans[i] +=M-R[i];
  150. 		}
  151.  
  152. 		for(int i =0; i < M; i++) cout << ans[i] << ((i == M-1)?"\n":" ");
  153. 	}
  154. }
  155.  
  156. // look at my code
  157. // my code is amazing
  158.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/qeUY2w
Codechef October Challenge 2017, LKYEDGE
language:
C++14 (gcc 8.3)
created:
7 years 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!