fork download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-8
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. #define dbl long double
  28. using namespace std;
  29. // mylittledoge
  30.  
  31. void constI(int R, vector< vector<int> > &son, vector< pair<int,int> > &I, vector<int> &D) {
  32. 	I[R].ss =I[R].ff+1;
  33. 	ALL_THE(son[R],it) {
  34. 		I[*it].ff =I[R].ss;
  35. 		D[I[*it].ff] =D[I[R].ff]+1;
  36. 		constI(*it,son,I,D);
  37. 		I[R].ss =I[*it].ss;}
  38. 	}
  39.  
  40. struct node {
  41. 	int son[2];
  42. 	int z,k,mod;
  43. 	pair<int,int> val;
  44. 	};
  45.  
  46. struct intervalac {
  47. 	vector<node> T;
  48.  
  49. 	void constI(int akt, vector<int> &A) {
  50. 		node n =T[akt];
  51. 		if(n.z == n.k-1) {
  52. 			T[akt].val =make_pair(A[n.z],n.z);
  53. 			return;}
  54. 		for(int i =0; i < 2; i++) {
  55. 			if(i == 0) n.k =(n.z+n.k)/2;
  56. 			else {n.z =n.k; n.k =T[akt].k;}
  57. 			T[akt].son[i] =T.size();
  58. 			T.push_back(n);
  59. 			constI(T[akt].son[i],A);}
  60. 		T[akt].val =max(T[T[akt].son[0]].val,T[T[akt].son[1]].val);}
  61.  
  62. 	intervalac(int N, vector<int> &A) {
  63. 		node n;
  64. 		n.mod =n.z =0;
  65. 		n.k =N;
  66. 		n.son[0] =n.son[1] =-1;
  67. 		n.val =make_pair(0,0);
  68. 		T.dibs(N*2+tisic);
  69. 		T.resize(1,n);
  70. 		constI(0,A);}
  71.  
  72. 	void upd(int akt) {
  73. 		node n =T[akt];
  74. 		if(n.mod == 0) return;
  75. 		T[akt].val.ff +=n.mod;
  76. 		for(int i =0; i < 2; i++) if(n.son[i] >= 0)
  77. 			T[n.son[i]].mod +=n.mod;
  78. 		T[akt].mod =0;}
  79.  
  80. 	void put(int akt, int zac, int kon, int val) {
  81. 		upd(akt);
  82. 		node n =T[akt];
  83. 		if(n.k <= zac || kon <= n.z) return;
  84. 		if(n.z == zac && kon == n.k) {
  85. 			T[akt].mod +=val;
  86. 			upd(akt);
  87. 			return;}
  88. 		put(n.son[0],zac,min(kon,(n.z+n.k)/2),val);
  89. 		put(n.son[1],max(zac,(n.z+n.k)/2),kon,val);
  90. 		upd(n.son[0]);
  91. 		upd(n.son[1]);
  92. 		T[akt].val =max(T[n.son[0]].val,T[n.son[1]].val);}
  93.  
  94. 	pair<int,int> get() {
  95. 		upd(0);
  96. 		return T[0].val;}
  97. 	};
  98.  
  99. int main() {
  100. 	cin.sync_with_stdio(0);
  101. 	cin.tie(0);
  102. 	int T;
  103. 	cin >> T;
  104. 	for(int t =0; t < T; t++) {
  105. 		int N,M,K;
  106. 		cin >> N >> M >> K;
  107. 		vector< vector<int> > G(N), son(N+1);
  108. 		vector<int> D(N);
  109. 		for(int i =0; i < M; i++) {
  110. 			int a,b;
  111. 			cin >> a >> b;
  112. 			G[--a].push_back(--b);
  113. 			G[b].push_back(a);
  114. 			D[a]++, D[b]++;}
  115.  
  116. 		queue<int> q;
  117. 		vector<int> par(N+1,-1);
  118. 		for(int i =0; i < N; i++) if(D[i] == 1) q.push(i), par[i] =-2;
  119. 		while(!q.empty()) {
  120. 			ALL_THE(G[q.front()],it) {
  121. 				D[*it]--;
  122. 				if(D[*it] == 1) q.push(*it), par[*it] =-2;
  123. 				if(D[*it] < 1) par[*it] =q.front(), son[q.front()].push_back(*it);}
  124. 			q.pop();}
  125. 		for(int i =0; i < N; i++) if(par[i] == -2) {
  126. 			son[N].push_back(i);
  127. 			par[i] =N;}
  128.  
  129. 		vector< pair<int,int> > I(N+1,make_pair(0,0));
  130. 		vector<int> dep(N+1,0), vis(N+1,1);
  131. 		constI(N,son,I,dep);
  132. 		vector<int> Ii(N+1);
  133. 		for(int i =0; i <= N; i++) if(I[i].ss != I[i].ff) Ii[I[i].ff] =i;
  134. 		vis[N] =0;
  135. 		for(int i =0; i < N; i++) if(par[i] == -1) vis[i] =0;
  136.  
  137. 		intervalac In(N+1,dep);
  138. 		for(int k =0; k < K; k++) {
  139. 			pair<int,int> nxtL =In.get();
  140. 			int akt =Ii[nxtL.ss];
  141. 			while(vis[akt]) {
  142. 				vis[akt] =0;
  143. 				In.put(0,I[akt].ff,I[akt].ss,-1);
  144. 				akt =par[akt];}
  145. 			}
  146.  
  147. 		int ans =0;
  148. 		for(int i =0; i < N; i++) if(vis[i]) ans++;
  149. 		cout << ans << "\n";}
  150. 	return 0;}
  151.  
  152. // look at my code
  153. // my code is amazing
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
2
6 6 1
1 2
2 3
1 3
1 4
4 5
1 6
11 11 3
1 2
2 3
1 3
1 4
4 5
2 6
3 7
7 8
7 9
8 10
9 11
stdout
copy 
1
1
https://ideone.com/0FVM0P
CT S02E08 F
language:
C++14 (gcc 8.3)
created:
10 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!