fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. template <typename... T> void read(T& ... t){ ((cin >> t), ...); }
  4. template <typename... T> void write(T ... t){ ((cout << t), ...); }
  5. //#define int long long
  6. #define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  7. #define size(x) (int)x.size()
  8. #define all(x) x.begin(),x.end()
  9. #define endl '\n'
  10. #define FOR(i,a,b) for(int i=a; i<=b; ++i)
  11. #define ROF(i,b,a) for(int i=b; i>=a; --i)
  12. using LL = long long;
  13. using pii = pair<int,int>;
  14. const int INF = 2e9;
  15. const int MAX_N = 2e4 +3;
  16.  
  17. struct Dsu {
  18. 	vector<int> _leader, _size;
  19. 	Dsu(int _n) {
  20. 		_leader.assign(_n+1,0);
  21. 		_size.assign(_n+1,0);
  22. 		FOR(i,1,_n){ _leader[i] = i; _size[i] = 1; }
  23. 	}
  24. 	int leader(int x) { return (_leader[x]==x) ? x : _leader[x]=leader(_leader[x]); }
  25. 	void unite(int x, int y) {
  26. 		x = leader(x);
  27. 		y = leader(y);
  28. 		if(x == y) return;
  29. 		_leader[y] = x;
  30. 		_size[x] += _size[y];
  31. 	}
  32. };
  33. template<typename T> struct SparseT{
  34. 	int n,lg;
  35. 	vector<vector<T>> arr;
  36. 	T neutral;
  37. 	function<T(T, T)> Combine;
  38. 	function<int(int, int)> Nxt;
  39. 	function<bool(int, int)>  HasNxt;
  40. 	SparseT(){}
  41. 	SparseT(int _n, T _neutral, function<T(T,T)>_combine,function<int(int,int)>_nxt,function<int(int,int)> _hasNxt){
  42. 		n = _n;
  43. 		lg = log2(_n);
  44. 		neutral = _neutral;
  45. 		arr.assign(lg+1, vector<T>(n+1, neutral));
  46. 		Combine = _combine;
  47. 		Nxt = _nxt;
  48. 		HasNxt = _hasNxt;
  49. 	}
  50. 	T& base(int node){
  51. 		return arr[0][node];
  52. 	}
  53. 	T get(int node, int len){
  54. 		T ans = neutral;
  55. 		while(len > 0){
  56. 			int jump = __builtin_ctz(len);
  57. 			len -= (1<<jump);
  58. 			ans = Combine(ans, arr[jump][node]);
  59. 			node = Nxt(node, jump);
  60. 		}
  61. 		return ans;
  62. 	}
  63. 	void computeAll(){
  64. 		for(int jump=1; jump<=lg; ++jump) for(int node=1; node<=n; ++node) if(HasNxt(node,jump)){
  65. 			int nxt = Nxt(node, jump-1);
  66. 			arr[jump][node] = Combine(arr[jump-1][node], arr[jump-1][nxt]);
  67. 		}
  68. 	}
  69. };
  70.  
  71. int n,m,q;
  72. vector<tuple<int,int,int>> e;
  73. vector<pii> adj[MAX_N];
  74. int dep[MAX_N];
  75.  
  76. SparseT<int> parent, minW;
  77.  
  78. Dsu dsu(MAX_N);
  79.  
  80. void explore(int u, int prv, int prvW, int depth){
  81. 	parent.base(u) = prv;
  82. 	minW.base(u) = prvW;
  83. 	dep[u] = depth;
  84. 	for(auto &[v,w]: adj[u]) if(v != prv) explore(v, u, w, depth+1);
  85. }
  86.  
  87. int lca(int x, int y) {
  88.     if (dep[y] > dep[x]) swap(x, y);
  89.     int diff = dep[x] - dep[y];
  90.     ROF(jump,parent.lg,0) if(diff&(1<<jump)) x = parent.arr[jump][x];
  91.  
  92. 	if (x == y) return x;
  93.  
  94. 	ROF(jump,parent.lg,0) if(parent.arr[jump][x] != parent.arr[jump][y]) {
  95.         x = parent.arr[jump][x]; 
  96. 		y = parent.arr[jump][y];
  97.     }
  98.     return parent.arr[0][x];
  99. }
  100.  
  101. int32_t main(){ FAST;
  102. 	read(n,m,q);
  103. 	FOR(mm,1,m){
  104. 		int u,v,w; read(u,v,w);
  105. 		e.emplace_back(u,v,w);
  106. 	}
  107.  
  108. 	sort(all(e), [&](auto &a, auto &b){ return get<2>(a) > get<2>(b); });
  109.  
  110. 	for(auto &[u,v,w]: e){
  111. 		if(dsu.leader(u) == dsu.leader(v)) continue;
  112. 		dsu.unite(u, v);
  113. 		adj[u].emplace_back(v,w);
  114. 		adj[v].emplace_back(u,w);
  115. 	}
  116.  
  117. 	parent = SparseT<int>(n,0,
  118. 	[&](int old,int cur){return cur;},
  119. 	[&](int node,int jump){return parent.arr[jump][node];},
  120. 	[&](int node,int jump){return dep[node] >= (1<<jump);});
  121. 	minW = SparseT<int>(n,INF,
  122. 	[&](int old,int cur){return min(old,cur);},
  123. 	[&](int node,int jump){return parent.arr[jump][node];},
  124. 	[&](int node,int jump){return dep[node] >= (1<<jump);});
  125.  
  126. 	explore(1, 1, INF, 1);
  127.  
  128. 	parent.computeAll();
  129. 	minW.computeAll();
  130.  
  131. 	FOR(qq,1,q){
  132. 		int u,v; read(u,v);
  133. 		int p = lca(u, v);
  134. 		int w1 = minW.get(u, dep[u]-dep[p]);
  135. 		int w2 = minW.get(v, dep[v]-dep[p]);
  136. 		write(min(w1, w2), endl);
  137. 	}
  138. }
Runtime error #stdin #stdout #stderr 0s 4340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/fOwLE0
language:
C++14 (gcc 8.3)
created:
4 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!