fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 200010
  4. #define pii pair<int,int>
  5. #define mp make_pair
  6. #define F first
  7. #define S second
  8. #define old _old
  9. #define new _new
  10. pair <int, pii> a[maxn];
  11. int typ[maxn];
  12. int par[maxn], val[maxn];
  13. vector <int> adj[maxn], cd[maxn];
  14. map <int, int> cost[maxn];
  15. int root (int v){
  16. 	if (par[v]==v) return v;
  17. 	return par[v]= root(par[v]);
  18. }
  19.  
  20. void merge (int u, int v){
  21. 	u= root(u);
  22. 	v= root(v);
  23. 	if (u==v) return;
  24. 	par[u]= v;
  25. }
  26.  
  27. void dfs (int v, int p){
  28. 	par[v]= p;
  29. 	for (int i=0; i<adj[v].size(); i++){
  30. 		int nt= adj[v][i];
  31. 		if (nt==p) continue;	
  32. 		cd[v].push_back(adj[v][i]);
  33. 		val[adj[v][i]]= cost[v][adj[v][i]];
  34. 		dfs(adj[v][i], v);
  35. 	}
  36. }
  37.  
  38. multiset <int> ans[maxn];
  39. multiset <int> ovr;
  40. set <int> cols[maxn];
  41. multiset <int> st[2*maxn];
  42. map <int, int> col[maxn];	
  43.  
  44. void print (){
  45. 	printf("%d\n", (*ovr.begin()));
  46. }
  47. int cur;
  48. int get (int v, int cl){
  49. 	int q= col[v][cl];
  50. 	if (q==0){
  51. 		cur++;
  52. 		col[v][cl]= cur;
  53. 		q= cur;
  54. 	}
  55. 	return q;
  56. }
  57.  
  58. int main(){
  59. 	freopen ("grass.in", "r", stdin);
  60. 	freopen ("grass.out", "w", stdout);
  61. 	cur= 0;		
  62. 	int n, m, k, q;
  63. 	scanf("%d %d %d %d", &n, &m ,&k, &q);
  64. 	for (int i=1; i<=m; i++){
  65. 		//cin>>a[i].S.F>>a[i].S.S>>a[i].F;
  66. 		scanf("%d %d %d", &a[i].S.F, &a[i].S.S, &a[i].F);
  67. 	}
  68. 	sort(a+1, a+m+1);
  69. 	for (int i=1; i<=n; i++){
  70. 		//cin>>typ[i];
  71. 		scanf("%d ", &typ[i]);
  72. 		par[i]= i;
  73. 	}
  74. 	for (int i=1; i<=m; i++){
  75. 		int u= a[i].S.F, v= a[i].S.S;
  76. 		if (root(u)==root(v)) continue;
  77. 		merge(u, v);
  78. 		adj[u].push_back(v);
  79. 		adj[v].push_back(u);
  80. 		cost[u][v]= cost[v][u]= a[i].F;
  81. 	}
  82. 	dfs(1, 0);
  83. 	for (int i=1; i<=n; i++){
  84. 		for (int j=0; j<cd[i].size(); j++){
  85. 			int nt= cd[i][j];
  86. 			int tp= get(i, typ[nt]);
  87. 			st[tp].insert(val[nt]);
  88. 			cols[i].insert(typ[nt]);
  89. 		}
  90. 		for (set <int> :: iterator it= cols[i].begin(); it!=cols[i].end(); it++){
  91. 			int t= *it;
  92. 			if (t!=typ[i]){
  93. 				int tp= get(i, t);
  94. 				ans[i].insert(*st[tp].begin());
  95. 			}				
  96. 		}
  97. 	}
  98. 	for (int i=1; i<=n; i++) if (!ans[i].empty()) ovr.insert(*ans[i].begin());
  99.  
  100. 	while (q--){
  101. 		int u, v;
  102. 		scanf("%d %d", &u, &v);
  103. 		if (typ[u]==v){
  104. 			print();
  105. 			continue;
  106. 		}
  107. 		int old= -1;
  108. 		if (ans[u].size()>0) old= *ans[u].begin();
  109. 		int del= -1;
  110. 		int tp= get(u, v);
  111. 		if (st[tp].size()>0) del= *st[tp].begin();
  112. 		int add= -1;
  113. 		tp= get(u, typ[u]);
  114. 		if (st[tp].size()>0) add= *st[tp].begin();
  115. 		if (del!=-1) {
  116. 			ans[u].erase(ans[u].find(del));
  117. 		}
  118. 		if (add!=-1) {
  119. 			ans[u].insert(add);
  120. 		}
  121. 		int new= -1;
  122. 		if (!ans[u].empty()) new= *ans[u].begin();
  123. 		if (old!=-1) ovr.erase(ovr.	find(old));
  124. 		if (new!=-1) ovr.insert(new);
  125.  
  126. 		if (u==1) {
  127. 			typ[u]= v;
  128. 			print();
  129. 			continue;
  130. 		}
  131. 		int p= par[u];
  132. 		tp= get(p, typ[u]);
  133. 		old= *st[tp].begin();
  134. 		int old2=-1;
  135. 		if (!ans[p].empty()) old2= *ans[p].begin();	  
  136. 		int old3= -1;
  137. 		tp= get(p, typ[u]);
  138. 		if (typ[u]!=typ[p]) old3= *st[tp].begin();
  139. 		st[tp].erase(st[tp].find(val[u]));
  140. 		if (old3!=-1){
  141. 			ans[p].erase(ans[p].find(old3));
  142. 			if (!st[tp].empty()) {
  143. 				ans[p].insert(*st[tp].begin());
  144. 			}
  145. 		}
  146. 		int old4= -1;
  147. 		tp= get(p, v);
  148. 		if (typ[p]!=v) {
  149. 			if (!st[tp].empty()) old4= *st[tp].begin();
  150. 		}  
  151. 		st[tp].insert(val[u]);
  152. 		if (typ[p]!=v){
  153. 			if (old4!=-1) {
  154. 				ans[p].erase(ans[p].find(old4));
  155. 			}
  156. 			ans[p].insert(*st[tp].begin());			
  157. 		}
  158. 		if (old2!=-1) ovr.erase(ovr.find(old2));
  159. 		if (!ans[p].empty()) ovr.insert(*ans[p].begin());
  160. 		typ[u]= v;
  161. 		print();
  162. 	}
  163. }
Runtime error #stdin #stdout 0.02s 86400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jDqaIn
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!