#include <stdio.h>
#include <stdlib.h>
#define N 1000001
#define N_ (1<<20)
int n, s, t, *eh[N], eo[N], dep[N], up[N], par[N], sz[N], hld[N], tin[N], temp,
st[N_ * 2], uu[N], vv[N], timer, aux[N];
void add(int p, int k) {
st[p += N_] += k;
for (; p /= 2; )
st[p] = st[p * 2] + st[p * 2 + 1];
}
int query(int l, int r) {
int z = 0;
l += N_;
r += N_ + 1;
for (; l < r; l /= 2, r /= 2) {
if (l & 1) z = z + st[l++];
if (r & 1) z = st[--r] + z;
}
return z;
}
int search_rightmost(int v, int l, int r, int k) {
if (l == r) return l;
if (st[v * 2 + 1] >= k) return search_rightmost(2 * v + 1, (l+r)/2 + 1, r, k);
else return search_rightmost(2 * v, l, (l+r)/2, k - st[v * 2 + 1]);
}
int search_leftmost(int v, int l, int r, int k) {
if (l == r) return l;
if (st[v * 2] >= k) return search_leftmost(2 * v, l, (l+r)/2, k);
else return search_leftmost(2 * v + 1, (l+r)/2+1, r, k - st[v * 2]);
}
int upper(int key_pos) {
return up[uu[key_pos]] == key_pos ? uu[key_pos] : vv[key_pos];
}
void pus(int i, int j) {
int o = eo[i]++;
if (!o) eh[i] = (int*)malloc(2 * sizeof**eh);
else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
eh[i][o] = j;
}
void dfs(int u, int p) {
sz[u] = 1;
dep[u] = dep[par[u] = p] + 1;
for (int j = 0; j < eo[u]; j += 2) if (eh[u][j] != p) {
up[eh[u][j]] = eh[u][j+1], dfs(eh[u][j], u), sz[u] += sz[eh[u][j]];
if (eh[u][0] == p || sz[eh[u][0]] < sz[eh[u][j]])
temp = eh[u][0], eh[u][0] = eh[u][j], eh[u][j] = temp;
}
}
void efs(int u, int h) {
aux[tin[u] = ++timer] = u;
hld[u] = h;
for (int j = 0; j < eo[u]; j += 2) if (eh[u][j] != par[u])
efs(eh[u][j], j ? eh[u][j] : h);
}
int lca(int u, int v) {
while (hld[u] != hld[v]) {
if (dep[hld[u]] > dep[hld[v]]) u = par[hld[u]];
else v = par[hld[v]];
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int query_path(int u, int v, int *a) {
int z = 0;
while (hld[u] != hld[v]) {
if (dep[hld[u]] < dep[hld[v]]) temp = u, u = v, v = temp;
z += query(tin[hld[u]], tin[u]);
u = par[hld[u]];
}
if (dep[u] < dep[v]) temp = u, u = v, v = temp;
z += query(tin[v] + 1, tin[u]);
if (NULL != a) *a = v;
return z;
}
int find_key(int s, int t) { /* first node that contain first key from s to t */
int cc, a = lca(s, t);
if (s != a) {
for (; hld[a] != hld[s]; s = par[hld[s]]) {
cc = query(tin[s] + 1, n);
int k = search_rightmost(1, 0, N_ - 1, cc + 1);
if (tin[s] >= k && k >= tin[hld[s]])
return up[aux[k]];
}
if (s != a) {
cc = query(tin[s] + 1, n);
int k = search_rightmost(1, 0, N_ - 1, cc + 1);
if (tin[s] >= k && k >= tin[a] + 1)
return up[aux[k]];
}
}
if (t != a) {
int stkl[40], stkr[40], so = 0;
for (; hld[a] != hld[t]; t = par[hld[t]])
stkl[so] = tin[hld[t]], stkr[so] = tin[t], ++so;
if (t != a) {
stkl[so] = tin[a] + 1, stkr[so] = tin[t];
++so;
}
for (int i = so - 1; i >= 0; --i) {
int l = stkl[i], r = stkr[i];
cc = query(0, l - 1);
int k = search_leftmost(1, 0, N_ - 1, cc + 1);
if (k >= l && k <= r) {
return up[aux[k]];
}
}
}
return 0;
}
int cur, z = 0, call = 0;
void go(int t) {
if (++call == 2000) {
puts("-1");
exit(0);
}
if (cur == t)
return;
int k;
while ((k = find_key(cur, t))) {
go(k);
int unlock = query_path(cur, uu[k], NULL) ? vv[k] : uu[k];
go(unlock);
add(tin[upper(k)], -1);
}
z += dist(cur, t);
cur = t;
}
int main() {
scanf("%d%d%d", &n, &s, &t);
for (int u, v, w, i = 1; i < n; ++i) {
scanf("%d%d%d", &u, &v, &w), pus(u, v), pus(u, w), pus(v, u), pus(v, w);
if (w)
uu[w] = u, vv[w] = v;
}
dfs(1, 1);
efs(1, 1);
for (int i = 1; i <= n; ++i)
if (up[i])
add(tin[i], 1);
cur = s;
go(t);
printf("%d", z);
}
Compilation message
Main.c: In function 'pus':
Main.c:46:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
46 | else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
| ~~^~~
Main.c: In function 'main':
Main.c:154:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | scanf("%d%d%d", &n, &s, &t);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:156:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%d%d%d", &u, &v, &w), pus(u, v), pus(u, w), pus(v, u), pus(v, w);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
22876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
22876 KB |
Output is correct |
| 3 |
Correct |
27 ms |
32028 KB |
Output is correct |
| 4 |
Correct |
28 ms |
32036 KB |
Output is correct |
| 5 |
Correct |
27 ms |
32084 KB |
Output is correct |
| 6 |
Correct |
27 ms |
32096 KB |
Output is correct |
| 7 |
Correct |
27 ms |
32196 KB |
Output is correct |
| 8 |
Correct |
27 ms |
32084 KB |
Output is correct |
| 9 |
Correct |
30 ms |
32348 KB |
Output is correct |
| 10 |
Correct |
27 ms |
32084 KB |
Output is correct |
| 11 |
Correct |
27 ms |
32092 KB |
Output is correct |
| 12 |
Correct |
23 ms |
33120 KB |
Output is correct |
| 13 |
Incorrect |
24 ms |
34388 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
22876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
22964 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
22876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
22876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
22876 KB |
Output is correct |
| 3 |
Correct |
27 ms |
32028 KB |
Output is correct |
| 4 |
Correct |
28 ms |
32036 KB |
Output is correct |
| 5 |
Correct |
27 ms |
32084 KB |
Output is correct |
| 6 |
Correct |
27 ms |
32096 KB |
Output is correct |
| 7 |
Correct |
27 ms |
32196 KB |
Output is correct |
| 8 |
Correct |
27 ms |
32084 KB |
Output is correct |
| 9 |
Correct |
30 ms |
32348 KB |
Output is correct |
| 10 |
Correct |
27 ms |
32084 KB |
Output is correct |
| 11 |
Correct |
27 ms |
32092 KB |
Output is correct |
| 12 |
Correct |
23 ms |
33120 KB |
Output is correct |
| 13 |
Incorrect |
24 ms |
34388 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
