fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  4. #define FORD(i,a,b) for(int i = (a); i >= (b); --i)
  5. #define RI(i,n) FOR(i,1,(n))
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7. #define mini(a,b) a=min(a,b)
  8. #define maxi(a,b) a=max(a,b)
  9. #define mp make_pair
  10. #define pb push_back
  11. #define st first
  12. #define nd second
  13. #define sz(w) (int) w.size()
  14. typedef vector<int> vi;
  15. typedef long long ll;
  16. typedef long double ld;
  17. typedef pair<int,int> pii;
  18. const int inf = 1e9 + 5;
  19. const int nax = 1e5 + 5;
  20.  
  21. int in_type[nax];
  22. vector<vi> queries[nax];
  23.  
  24. int g[nax];
  25. vi odw[nax];
  26. set<int> types[nax];
  27. int ans[nax];
  28. set<pair<int,int>> ready[nax];
  29.  
  30. int main() {
  31. 	int n, m, q;
  32. 	scanf("%d%d%d", &n, &m, &q);
  33. 	RI(i, q) ans[i] = -1;
  34. 	RI(i, n) scanf("%d", &in_type[i]);
  35. 	vector<vi> roads;
  36. 	REP(_, m) {
  37. 		int a, b, cost;
  38. 		scanf("%d%d%d", &a, &b, &cost);
  39. 		roads.pb(vi{cost,a,b});
  40. 	}
  41. 	RI(i, q) {
  42. 		int a, b, cost;
  43. 		scanf("%d%d%d", &a, &b, &cost);
  44. 		queries[a].pb(vi{b,cost,i});
  45. 		queries[b].pb(vi{a,cost,i});
  46. 	}
  47.  
  48. 	sort(roads.begin(), roads.end());
  49. 	RI(i, n) {
  50. 		odw[i].pb(i);
  51. 		g[i] = i;
  52. 		types[i].insert(in_type[i]);
  53. 	}
  54. 	for(vi & road : roads) {
  55. 		int a = g[road[1]];
  56. 		int b = g[road[2]];
  57. 		int cost = road[0];
  58. 		if(a == b) continue;
  59. 		if(sz(odw[a]) > sz(odw[b])) swap(a,b);
  60. 		// a mniejsze
  61. 		for(pii p : ready[a])
  62. 			ready[b].insert(p);
  63. 		ready[a].clear();
  64. 		for(int x : odw[a]) {
  65. 			g[x] = b;
  66. 			odw[b].pb(x);
  67. 		}
  68. 		for(int x : types[a])
  69. 			types[b].insert(x);
  70. 		types[a].clear();
  71.  
  72. 		for(int x : odw[a])
  73. 			for(vi & query : queries[x]) {
  74. 				int y = query[0];
  75. 				int least = query[1];
  76. 				int q_id = query[2];
  77. 				if(g[x] == g[y] && ans[q_id] == -1) {
  78. 					if(sz(types[b])>=least)
  79. 						ans[q_id] = cost;
  80. 					else ready[b].insert(mp(least, q_id));
  81. 				}
  82. 			}
  83.  
  84. 		odw[a].clear();
  85.  
  86. 		while(!ready[b].empty()) {
  87. 			auto it = ready[b].begin();
  88. 			pii p = *it;
  89. 			if(p.first > sz(types[b])) break;
  90. 			ready[b].erase(it);
  91. 			if(ans[p.second] == -1)
  92. 				ans[p.second] = cost;
  93. 		}
  94. 	}
  95. 	RI(i, q) printf("%d\n", ans[i]);
  96. 	return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 11672KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/OgU6lT
language:
C++14 (gcc 8.3)
created:
8 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!