fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <queue>
  4. #include <time.h>
  5. #include <algorithm>
  6. using namespace std;
  7. #define MN 30005
  8. #define MQ 300005
  9. int n, m, L, N;
  10. int bt[4 * MN];
  11. int w[MN], c[MN], chk[MN], d[MN], bn, par[MN], head[MN], number[MN], line[MN], depth[MN];
  12. char S[22];
  13. struct Query {
  14. 	int T, A, B;
  15. } q[MQ];
  16. int u(int x) {
  17. 	if (c[x] == x) return x;
  18. 	c[x] = u(c[x]);
  19. 	return c[x];
  20. }
  21. vector <int> v[MN];
  22. void dfs(int x, int dad) {
  23. 	int split = 0;
  24. 	number[x] = ++N;
  25. 	head[N] = number[dad];
  26. 	line[N] = L;
  27. 	chk[x] = 1;
  28. 	for (int i = 0; i < v[x].size(); i++) {
  29. 		if (chk[v[x][i]] == 0) {
  30. 			depth[N + 1] = depth[number[x]] + 1;
  31. 			par[N + 1] = number[x];
  32. 			if (!split) {
  33. 				dfs(v[x][i], dad);
  34. 				split = 1;
  35. 			}
  36. 			else {
  37. 				++L;
  38. 				dfs(v[x][i], v[x][i]);
  39. 			}
  40. 		}
  41. 	}
  42. }
  43. void upd(int x, int y) {
  44. 	while (x) bt[x] += y, x /= 2;
  45. }
  46. int sum(int lo, int hi) {
  47. 	int ret = 0;
  48. 	while (lo <= hi) {
  49. 		if (lo == hi) { ret += bt[lo]; break; }
  50. 		if (lo & 1) ret += bt[lo++];
  51. 		if (!(hi & 1)) ret += bt[hi--];
  52. 		lo /= 2; hi /= 2;
  53. 	}
  54. 	return ret;
  55. }
  56. int main() {
  57. 	scanf("%d", &n);
  58. 	bn = 1; while (bn < n) bn *= 2; bn--;
  59. 	for (int i = 1; i <= n; i++) {
  60. 		scanf("%d", &w[i]);
  61. 		c[i] = i;
  62. 		par[i] = -1;
  63. 	}
  64. 	scanf("%d", &m);
  65. 	for (int i = 1; i <= m; i++) {
  66. 		scanf("%s%d%d", S, &q[i].A, &q[i].B);
  67. 		if (S[0] == 'p') q[i].T = 0;
  68. 		else if (S[0] == 'b') q[i].T = 1;
  69. 		else q[i].T = 2;
  70. 	}
  71. 	for (int i = 1; i <= m; i++) {
  72. 		if (q[i].T == 1) {
  73. 			int A = u(q[i].A), B = u(q[i].B);
  74. 			if (A != B) {
  75. 				c[B] = A;
  76. 				v[q[i].A].push_back(q[i].B);
  77. 				v[q[i].B].push_back(q[i].A);
  78. 			}
  79. 		}
  80. 	}
  81. 	L = 1;
  82. 	for (int i = 1; i <= n; i++) {
  83. 		if (!number[i]) {
  84. 			depth[N + 1] = 1;
  85. 			dfs(i, i);
  86. 		}
  87. 	}
  88. 	for (int i = 1; i <= n; i++) {
  89. 		upd(bn + number[i], w[i]);
  90. 		c[i] = i;
  91. 	}
  92. 	for (int i = 1; i <= m; i++) {
  93. 		if (q[i].T == 0) {
  94. 			upd(bn + number[q[i].A], q[i].B - bt[bn + number[q[i].A]]);
  95. 		}
  96. 		else if (q[i].T == 1) {
  97. 			int A = u(number[q[i].A]), B = u(number[q[i].B]);
  98. 			if (A == B) puts("no");
  99. 			else {
  100. 				c[B] = A;
  101. 				puts("yes");
  102. 			}
  103. 		}
  104. 		else {
  105. 			int A = u(number[q[i].A]), B = u(number[q[i].B]);
  106. 			if (A != B) puts("impossible");
  107. 			else {
  108. 				int x = number[q[i].A], y = number[q[i].B];
  109. 				int res = 0;
  110. 				while (line[x] != line[y]) {
  111. 					if (depth[head[x]] < depth[head[y]]) swap(x, y);
  112. 					res += sum(bn + head[x], bn + x);
  113. 					x = par[head[x]];
  114. 				}
  115. 				if (x > y) swap(x, y);
  116. 				res += sum(bn + x, bn + y);
  117. 				printf("%d\n", res);
  118. 			}
  119. 		}
  120. 	}
  121. }
Success #stdin #stdout 0s 8624KB
comments (?)
stdin
copy 
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
stdout
copy 
4
impossible
yes
6
yes
yes
15
yes
15
16
https://ideone.com/cea3Ld
language:
C++ (gcc 8.3)
created:
8 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!