fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pu push
  3. #define pf push_front
  4. #define pb push_back
  5. #define pof pop_front
  6. #define pob pop_back
  7. #define fi first
  8. #define se second
  9. #define el cout<<"\n"
  10. #define ll long long 
  11. #define ull unsigned long long
  12. #define ld long double
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(x, i) (((x)>>(i))&1)	
  15. #define SET_ON(x, i) ((x)|MASK(i))
  16. #define SET_OFF(x, i) ((x)&~MASK(i))
  17. #define c_bit(i) __builtin_popcount(i)
  18. const int MAX_SIZE = 100010;
  19. const int LOG = 18;
  20. const int inf = (int)1e9+7;
  21. using namespace std;
  22.  
  23. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  24.  
  25. long long random(long long l, long long r){
  26. 	return uniform_int_distribution<long long>(l, r)(rng);
  27. }
  28.  
  29. template<class T1, class T2>
  30.     bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
  31. template<class T1, class T2>
  32.     bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}
  33.  
  34. int numNode, numQuery, length;
  35. int nodeID[MAX_SIZE], height[MAX_SIZE];
  36. int rmq[2*MAX_SIZE+3][LOG], valueID[2*MAX_SIZE+3];
  37.  
  38. vector<int>adj[MAX_SIZE];
  39.  
  40. // 13
  41. // 1 3
  42. // 1 5
  43. // 1 2
  44. // 3 6
  45. // 6 9
  46. // 5 4
  47. // 5 7
  48. // 5 13
  49. // 4 8
  50. // 4 10
  51. // 7 11
  52. // 7 12
  53.  
  54. void pre_dfs(int u, int par){
  55. 	++length;
  56. 	nodeID[u] = length;
  57. 	valueID[length] = u;
  58. 	for (auto v:adj[u]) if (v!=par){
  59. 		height[v] = height[u] + 1;
  60. 		pre_dfs(v, u);
  61. 		++length;
  62. 		valueID[length] = u;
  63. 	}
  64. }
  65.  
  66. int min_high_node(int u, int v){
  67. 	if (height[u] < height[v]) return u;
  68. 	return v;
  69. }
  70.  
  71. int getLCA(int u, int v){
  72. 	int l = nodeID[u], r = nodeID[v]; if (l>r) swap(l, r);
  73. 	int k = 31 - __builtin_clz(r-l+1);
  74. 	return min_high_node(rmq[l][k], rmq[r-MASK(k)+1][k]);
  75. }
  76.  
  77. void ilovesunshine(){
  78. 	cin>>numNode;
  79. 	for (int i=1; i<numNode; ++i){
  80. 		int u, v; cin>>u>>v;
  81. 		adj[u].pb(v);
  82. 		adj[v].pb(u);	
  83. 	}
  84.  
  85. 	pre_dfs(1, 0);
  86.  
  87. 	for (int i=1; i<=length; ++i){
  88. 		rmq[i][0] = valueID[i];
  89. 	}
  90.  
  91. 	for (int j=1; j<=LOG; ++j){
  92. 		for (int i=1; i+MASK(j)-1<=length; ++i){
  93. 			rmq[i][j] = min_high_node(rmq[i][j-1], rmq[i+MASK(j-1)][j-1]);
  94. 		} 	
  95. 	}
  96.  
  97. 	cin>>numQuery;
  98. 	while (numQuery--){
  99. 		int u, v; cin>>u>>v;
  100. 		cout<<getLCA(u, v)<<"\n";
  101. 	}
  102. }
  103.  
  104. int main(){
  105. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  106. 	ilovesunshine();
  107. 	return 0;
  108. }
Success #stdin #stdout 0.01s 8016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fjPAC0
LCA O(1) _ Tame
language:
C++14 (gcc 8.3)
created:
6 hours 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!