fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb(x) push_back(x)
  5. #define mp(a, b) make_pair(a, b)
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<ll> vll;
  10. typedef vector<int> vi;
  11. typedef pair<ll, ll> pll;
  12. const int MOD = 1e9 + 7;
  13. const int LOG = 20;
  14. vector< vi > adj;
  15. vi level;
  16. vi parent;
  17. vector<bool> visited;
  18. vector< vi > up;
  19. vector< vi > lca_right;
  20. vector< vi > lca_left;
  21. int n;
  22. void bfs(int src) {
  23. 	queue<int> q;
  24. 	q.push(src);
  25. 	while(!q.empty()) {
  26. 		int u = q.front();
  27. 		visited[u] = true;
  28. 		q.pop();
  29. 		for(auto v: adj[u]) {
  30. 			if(!visited[v]) {
  31. 				level[v] = level[u] + 1;
  32. 				parent[v] = u;
  33. 				up[v][0] = u;
  34. 				q.push(v);
  35. 			}
  36. 		}
  37. 	}
  38. }
  39. void fill_up() {
  40. 	for(int i = 1; i < LOG; ++i)
  41. 		for(int j = 0; j < n; ++j)
  42. 			if(up[j][i - 1] != -1)
  43. 				up[j][i] = up[up[j][i - 1]][i - 1];
  44. }
  45. int walk(int u, int k) {
  46. 	int node = u;
  47. 	int ct = 0;
  48. 	while(k) {
  49. 		if(k % 2)
  50. 			node = up[node][ct];
  51. 		ct++;
  52. 		if(ct > LOG)
  53. 			return -1;
  54. 		k /= 2;
  55. 	}
  56. 	return node;
  57. }
  58. int lca(int u, int v) {
  59. 	if(level[u] > level[v]) 
  60. 		swap(u, v);
  61. 	int diff = abs(level[u] - level[v]);
  62. 	v = walk(v, diff);
  63. 	if(u == v)
  64. 		return u;
  65. 	while(1) {
  66. 		int jump = 0;
  67. 		for(int k = 0; k < LOG; ++k) {
  68. 			if(up[u][k] == up[v][k])
  69. 				break;
  70. 			jump = k;
  71. 		}
  72. 		u = up[u][jump];
  73. 		v = up[v][jump];
  74. 		if(u == v)
  75. 			return u;
  76. 	}
  77. }
  78. vll two(LOG + 1, 1);
  79. void fill_up_sparse() {
  80. 	for(int i = 0; i < n; ++i) {
  81. 		lca_right[i][0] = i;
  82. 		lca_left[i][0] = i;
  83. 	}
  84.  
  85. 	for(int i = 1; i <= LOG; ++i)
  86. 		two[i] = two[i - 1] * 2ll;
  87.  
  88. 	for(int i = 1; i < LOG; ++i) {
  89. 		for(int j = 0; j < n; ++j) {
  90. 			if(lca_right[j][i - 1] != -1 and ((j + two[i - 1]) < n) and (lca_right[j + two[i - 1]][i - 1] != -1))
  91. 				lca_right[j][i] = lca(lca_right[j][i - 1], lca_right[j + two[i - 1]][i - 1]);
  92. 		}
  93. 	}
  94.  
  95. 	for(int i = 1; i < LOG; ++i) 
  96. 		for(int j = n - 1; j >= 0; j--) 
  97. 			if(lca_left[j][i - 1] != -1 and (j - two[i - 1]) >= 0 and lca_left[j - two[i - 1]][i -1] != -1)
  98. 				lca_left[j][i] = lca(lca_left[j][i - 1], lca_left[j - two[i - 1]][i -1]);
  99. }
  100. int lca_range(int l, int r) {
  101. 	int len = 0;
  102. 	for(int i = 0; i < LOG; ++i) {
  103. 		if(l + two[i] > r)
  104. 			break;
  105. 		len = i;
  106. 	}
  107. 	// if(l == 0 and r == 8)
  108. 	// 	cout << "***" << len << " " << lca_right[l][len] << " " << lca_left[r][len] << endl;
  109. 	return lca(lca_right[l][len], lca_left[r][len]);
  110. }
  111. int main() {
  112. 	std :: ios_base :: sync_with_stdio(false);
  113. 	cin.tie(NULL), cout.tie(NULL);
  114. 	cin >> n;
  115. 	adj.assign(n, vi());
  116. 	level.assign(n, 0);
  117. 	parent.assign(n, -1);
  118. 	visited.assign(n, false);
  119. 	up.assign(n, vi(LOG, -1));
  120. 	lca_left.assign(n, vi(LOG, -1));
  121. 	lca_right.assign(n, vi(LOG, -1));
  122. 	int q;
  123. 	cin >> q;
  124. 	int x, y;
  125. 	for(int i = 2; i <= n; ++i) {
  126. 		cin >> x;
  127. 		y = i;
  128. 		x--, y--;
  129. 		adj[x].pb(y);
  130. 		adj[y].pb(x);
  131. 	}
  132. 	bfs(0);
  133. 	fill_up();
  134. 	fill_up_sparse();
  135. 	int l, r;
  136. 	while(q--) {
  137. 		cin >> l >> r;
  138. 		l--, r--;
  139. 		int low = l;
  140. 		int high = r;
  141. 		int lca_LR = lca_range(l, r);
  142. 		int left = -1;
  143. 		int right = -1;
  144. 		while(low < high) {
  145. 			int mid = low + (high - low + 1) / 2;
  146. 			if(lca_range(l, mid) == lca_LR)
  147. 				high = mid - 1;
  148. 			else 
  149. 				low = mid;
  150. 		}
  151. 		if(lca_range(l, low) != lca_LR)
  152. 			left = low;
  153. 		if(left != -1 and left == r - 1) {
  154. 			cout << r + 1 << " " << level[lca_range(l, left)] << endl;
  155. 			continue;
  156. 		}
  157. 		low = l;
  158. 		high = r;
  159. 		while(low < high) {
  160. 			int mid = low + (high - low) / 2;
  161. 			if(lca_range(mid, r) == lca_LR)
  162. 				low = mid + 1;
  163. 			else
  164. 				high = mid;
  165. 		}
  166. 		if(lca_range(low, r) != lca_LR)
  167. 			right = low;
  168. 		if(right != -1 and right == l + 1) {
  169. 			cout << l + 1 << " " << level[lca_range(right, r)] << endl;
  170. 			continue;
  171. 		}
  172. 		if(left + 1 == right - 1) {
  173. 			cout << left + 2 << " " << level[lca(lca_range(l, left), lca_range(right, r))] << endl;
  174. 			continue;	
  175. 		}
  176. 		cout << l + 1 << " " << level[lca_LR] << endl;
  177. 	}
  178. 	return 0;
  179. }
  180.  
Runtime error #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kr0ZCY
language:
C++14 (gcc 8.3)
created:
6 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!