fork download
copy 
  1.  
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5.  
  6. using namespace std;
  7.  
  8. struct node {
  9. 	int data;
  10. 	node *next;
  11. } *ge[500000];
  12.  
  13. int pre[500000][19], rank[500000], belong[500000], len[500000];
  14. int queue[500000], root[500000], depth[500000], next[500000];
  15. bool v[500000];
  16.  
  17. void insertEdge(int a, int b) {
  18. 	static node buf[500000];
  19. 	static int top = 0;
  20. 	node *p = &buf[top ++];
  21. 	p->data = b;
  22. 	p->next = ge[a];
  23. 	ge[a] = p;
  24. }
  25.  
  26. int lca(int a, int b) {
  27. 	if (depth[a] < depth[b]) swap(a, b);
  28. 	int lg = 0;
  29. 	while (1 << lg <= depth[a]) lg ++;
  30. 	lg --;
  31. 	for (int i = lg; i >= 0; i --)
  32. 		if (depth[a] - (1 << i) >= depth[b]) a = pre[a][i];
  33. 	if (a == b) return a;
  34. 	for (int i = lg; i >= 0; i --)
  35. 		if (pre[a][i] != -1 && pre[a][i] != pre[b][i]) {
  36. 			a = pre[a][i];
  37. 			b = pre[b][i];
  38. 		}
  39. 	return pre[a][0];
  40. }
  41.  
  42. int main() {
  43. 	int n, q;
  44. 	scanf("%d%d", &n, &q);
  45. 	for (int i = 0; i < n; i ++) ge[i] = 0;
  46. 	for (int i = 0; i < n; i ++) {
  47. 		scanf("%d", &next[i]);
  48. 		next[i] --;
  49. 		insertEdge(next[i], i);
  50. 	}
  51.  
  52. 	memset(v, false, sizeof(v));
  53. 	memset(pre, -1, sizeof(pre));
  54. 	int tot = 0;
  55. 	for (int i = 0; i < n; i ++)
  56. 		if (! v[i]) {
  57. 			int start = i;
  58. 			while (! v[start]) {
  59. 				v[start] = true;
  60. 				start = next[start];
  61. 			}
  62. 			int now = i;
  63. 			while (v[now]) {
  64. 				v[now] = false;
  65. 				now = next[now];
  66. 			}
  67. 			len[tot] = 0;
  68. 			now = start;
  69. 			while (! v[now]) {
  70. 				rank[now] = len[tot];
  71. 				queue[len[tot] ++] = now;
  72. 				root[now] = now;
  73. 				belong[now] = tot;
  74. 				depth[now] = 0;
  75. 				v[now] = true;
  76. 				now = next[now];
  77. 			}
  78. 			for (int head = 0, tail = len[tot]; head < tail; head ++)
  79. 				for (node *p = ge[queue[head]]; p; p = p->next)
  80. 					if (! v[p->data]) {
  81. 						root[p->data] = root[queue[head]];
  82. 						belong[p->data] = tot;
  83. 						depth[p->data] = depth[queue[head]] + 1;
  84. 						pre[p->data][0] = queue[head];
  85. 						for (int j = 1; 1 << j <= depth[p->data]; j ++)
  86. 							pre[p->data][j] = pre[pre[p->data][j-1]][j-1];
  87. 						v[p->data] = true;
  88. 						queue[tail ++] = p->data;
  89. 					}
  90. 			tot ++;
  91. 		}
  92.  
  93. 	for (int i = 0; i < q; i ++) {
  94. 		int a, b;
  95. 		scanf("%d%d", &a, &b);
  96. 		a --;
  97. 		b --;
  98. 		if (belong[a] != belong[b]) {
  99. 			printf("-1 -1\n");
  100. 			continue;
  101. 		}
  102. 		if (root[a] == root[b]) {
  103. 			int t = lca(a, b);
  104. 			printf("%d %d\n", depth[a] - depth[t], depth[b] - depth[t]);
  105. 		} else {
  106. 			int x = root[a], y = root[b];
  107. 			int s11, s12, s21, s22;
  108. 			if (rank[x] < rank[y]) {
  109. 				s11 = depth[a] + rank[y] - rank[x];
  110. 				s12 = depth[b];
  111. 				s21 = depth[a];
  112. 				s22 = depth[b] + (len[belong[a]] - (rank[y] - rank[x]));
  113. 			} else {
  114. 				s11 = depth[a];
  115. 				s12 = depth[b] + rank[x] - rank[y];
  116. 				s21 = depth[a] + (len[belong[a]] - (rank[x] - rank[y]));
  117. 				s22 = depth[b];
  118. 			}
  119. 			if (max(s11, s12) > max(s21, s22)) {
  120. 				swap(s11, s21);
  121. 				swap(s12, s22);
  122. 			}
  123. 			if (max(s11, s12) == max(s21, s22) && min(s11, s12) > min(s21, s22)) {
  124. 				swap(s11, s21);
  125. 				swap(s12, s22);
  126. 			}
  127. 			if (max(s11, s12) == max(s21, s22) && min(s11, s12) == min(s21, s22) && s21 >= s22) {
  128. 				swap(s11, s21);
  129. 				swap(s12, s22);
  130. 			}
  131. 			printf("%d %d\n", s11, s12);
  132. 		}
  133. 	}
  134.  
  135. 	return 0;
  136. }
  137.  
Success #stdin #stdout 0.04s 59856KB
comments (?)
stdin
copy 
12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5
stdout
copy 
2 3
1 2
2 2
0 1
-1 -1
https://ideone.com/n96Ju
language:
C++ (gcc 8.3)
created:
14 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!