fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. class unionfind{
  11. public:
  12. 	int* o;
  13. 	int* r;
  14.  
  15. 	void init(int n){
  16. 		o = new int[n + 10];
  17. 		r = new int[n + 10];
  18. 		for (int i = 0; i < n + 10; i++){
  19. 			o[i] = -1;
  20. 			r[i] = 0;
  21. 		}
  22. 	}
  23.  
  24. 	int find(int n){
  25. 		if (o[n] < 0) return n;
  26. 		else return o[n] = find(o[n]);
  27. 	}
  28.  
  29. 	void unit(int a, int b){
  30. 		if (r[a] == r[b]){
  31. 			r[a]++;
  32. 			o[b] = a;
  33. 		}
  34. 		else if (r[a] > r[b]) o[b] = a;
  35. 		else o[a] = b;
  36. 	}
  37.  
  38. 	void del(){
  39. 		delete[] o;
  40. 		delete[] r;
  41. 	}
  42. };
  43.  
  44. pair<int, int> miti[3333333];
  45. ll gg[3333333];
  46. int jun[3333333];
  47. bool ok[3333333];
  48. vector<int> mw[1111111];
  49. bool table[1111111];
  50.  
  51. int main(){
  52. 	int n, m, q, p;
  53. 	scanf("%d%d%d%d", &n, &m, &q, &p);
  54. 	for (int i = 0; i < m; i++){
  55. 		int a, b;
  56. 		scanf("%d%d", &a, &b);
  57. 		a--;
  58. 		b--;
  59. 		miti[i] = make_pair(a, b);
  60. 		gg[i] = 0;
  61. 		mw[a].push_back(b);
  62. 		mw[b].push_back(a);
  63. 	}
  64. 	for (int i = 0; i < q; i++){
  65. 		int d;
  66. 		ll g;
  67. 		scanf("%d%lld", &d, &g);
  68. 		d--;
  69. 		jun[i] = d;
  70. 		gg[d] = g;
  71. 	}
  72. 	unionfind ufa;
  73. 	ufa.init(n);
  74. 	for (int i = 0; i < m; i++){
  75. 		if (gg[i] == 0){
  76. 			int w1 = ufa.find(miti[i].first);
  77. 			int w2 = ufa.find(miti[i].second);
  78. 			if (w1 != w2){
  79. 				ufa.unit(w1, w2);
  80. 			}
  81. 		}
  82. 	}
  83. 	for (int i = q - 1; i >= 0; i--){
  84. 		pair<int, int> w = miti[jun[i]];
  85. 		int w1 = ufa.find(w.first);
  86. 		int w2 = ufa.find(w.second);
  87. 		if (w1 != w2){
  88. 			ufa.unit(w1, w2);
  89. 			ok[i] = false;
  90. 		}
  91. 		else ok[i] = true;
  92. 	}
  93. 	ufa.del();
  94. 	ufa.init(n);
  95. 	for (int i = 0; i < q; i++){
  96. 		pair<int, int> w = miti[jun[i]];
  97. 		int w1 = ufa.find(w.first);
  98. 		int w2 = ufa.find(w.second);
  99. 		if (w1 == w2 || ok[i]) gg[jun[i]] = -1;
  100. 		else ufa.unit(w1, w2);
  101. 	}
  102. 	ufa.del();
  103. 	ufa.init(n + 1);
  104. 	for (int i = 0; i < n; i++){
  105. 		if (n - mw[i].size() < 3000){
  106. 			for (int j = 0; j < n; j++) table[j] = true;
  107. 			int l = mw[i].size();
  108. 			for (int j = 0; j < l; j++) table[mw[i][j]] = false;
  109. 			for (int j = 0; j < n; j++){
  110. 				if (table[j]){
  111. 					int w1 = ufa.find(i);
  112. 					int w2 = ufa.find(j);
  113. 					if (w1 != w2){
  114. 						ufa.unit(w1, w2);
  115. 					}
  116. 				}
  117. 			}
  118. 		}
  119. 		else{
  120. 			int w1 = ufa.find(i);
  121. 			int w2 = ufa.find(n);
  122. 			if (w1 != w2){
  123. 				ufa.unit(w1, w2);
  124. 			}
  125. 		}
  126. 	}
  127. 	ll res = 0;
  128. 	vector<ll> vw;
  129. 	vector<pair<ll, int> > vv;
  130. 	for (int i = 0; i < m; i++){
  131. 		if (gg[i] >= 0){
  132. 			int w1 = ufa.find(miti[i].first);
  133. 			int w2 = ufa.find(miti[i].second);
  134. 			if (w1 != w2) vv.push_back(make_pair(gg[i], i));
  135. 			else vw.push_back(gg[i]);
  136. 		}
  137. 	}
  138. 	sort(vv.begin(), vv.end());
  139. 	int lw = vv.size();
  140. 	for (int i = 0; i < lw; i++){
  141. 		int w1 = ufa.find(miti[vv[i].second].first);
  142. 		int w2 = ufa.find(miti[vv[i].second].second);
  143. 		if (w1 != w2){
  144. 			ufa.unit(w1, w2);
  145. 			res += vv[i].first;
  146. 		}
  147. 		else vw.push_back(vv[i].first);
  148. 	}
  149. 	sort(vw.begin(), vw.end());
  150. 	lw = vw.size();
  151. 	for (int i = 0; i < lw - p; i++){
  152. 		res += vw[i];
  153. 	}
  154. 	printf("%lld\n", res);
  155. 	return 0;
  156. }
  157.  
Success #stdin #stdout 0.04s 85952KB
comments (?)
stdin
copy 
3 3 2 0
3 1
2 3
2 1
3 15
2 10
stdout
copy 
10
https://ideone.com/G9O6CO
language:
C++ (gcc 8.3)
created:
8 years 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!