/tmp/solutions/build/jump_on_tree-slow.cpp:
1| |#include <common.h>
2| |prelude;
3| |
4| |namespace {
5| |
6| |constexpr int N = 5e5;
7| |
8| |struct {
9| | int to;
10| | int nxt;
11| |} edge[N * 2];
12| |int head[N];
13| |int size[N];
14| |int depth[N];
15| |int heavy[N];
16| |int ances[N];
17| |int parent[N];
18| |int node2id[N];
19| |int id2node[N];
20| |int id;
21| |
22| 70|def build_step_1(int u, int d, int p) -> void {
23| 70| size[u] = 1;
24| 70| depth[u] = d;
25| 70| parent[u] = p;
26| 208| for (int e = head[u]; e; e = edge[e].nxt) {
^138
------------------
| Branch (26:25): [True: 66.35%, False: 33.65%]
------------------
27| 138| if (int v = edge[e].to; v != p) {
------------------
| Branch (27:29): [True: 50.00%, False: 50.00%]
------------------
28| 69| build_step_1(v, d + 1, u);
29| 69| size[u] += size[v];
30| 69| if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
^34
------------------
| Branch (30:11): [True: 50.72%, False: 49.28%]
| Branch (30:28): [True: 32.35%, False: 67.65%]
------------------
31| 46| heavy[u] = v;
32| 46| }
33| 69| }
34| 138| }
35| 70|}
36| |
37| 70|def build_step_2(int u, int a, int p) -> void {
38| 70| node2id[u] = id;
39| 70| id2node[id] = u;
40| 70| ++id;
41| 70| ances[u] = a;
42| 70| if (heavy[u]) build_step_2(heavy[u], a, u);
^35
------------------
| Branch (42:7): [True: 50.00%, False: 50.00%]
------------------
43| 208| for (int e = head[u]; e; e = edge[e].nxt) {
^138
------------------
| Branch (43:25): [True: 66.35%, False: 33.65%]
------------------
44| 138| if (int v = edge[e].to; v != heavy[u] && v != p) {
^103
------------------
| Branch (44:29): [True: 74.64%, False: 25.36%]
| Branch (44:46): [True: 33.01%, False: 66.99%]
------------------
45| 34| build_step_2(v, v, u);
46| 34| }
47| 138| }
48| 70|}
49| |
50| 500k|def lca(int u, int v) -> int {
51| 1.64M| while (ances[u] != ances[v]) {
------------------
| Branch (51:10): [True: 69.59%, False: 30.41%]
------------------
52| 1.14M| if (depth[ances[u]] > depth[ances[v]]) {
------------------
| Branch (52:9): [True: 50.03%, False: 49.97%]
------------------
53| 572k| u = parent[ances[u]];
54| 572k| } else {
55| 571k| v = parent[ances[v]];
56| 571k| }
57| 1.14M| }
58| 500k| return depth[u] < depth[v] ? u : v;
^185k^314k
------------------
| Branch (58:10): [True: 37.19%, False: 62.81%]
------------------
59| 500k|}
60| |
61| 43.0k|def jump(int u, int d) -> int {
62| 63.3k| while (depth[ances[u]] > d) {
------------------
| Branch (62:10): [True: 32.03%, False: 67.97%]
------------------
63| 20.2k| u = parent[ances[u]];
64| 20.2k| }
65| 43.0k| return id2node[node2id[u] - depth[u] + d];
66| 43.0k|}
67| |
68| |} // namespace
69| |
70| 1|int main() {
71| 1| rd rd;
72| 1| wt wt;
73| 1| int n = rd.uh();
74| 1| int q = rd.uh();
75| 1|#ifdef LOCAL
76| 1| id = 0;
77| 1| std::memset(head, 0, 4 * n);
78| 1| std::memset(heavy, 0, 4 * n);
79| 1| std::memset(parent, 0, 4 * n);
80| 1|#endif
81| 70| for (int i = 1; i < n; ++i) {
^69
------------------
| Branch (81:19): [True: 98.57%, False: 1.43%]
------------------
82| 69| int a = rd.uh();
83| 69| int b = rd.uh();
84| 69| edge[i * 2 | 0] = {b, head[a]}, head[a] = i * 2 | 0;
85| 69| edge[i * 2 | 1] = {a, head[b]}, head[b] = i * 2 | 1;
86| 69| }
87| 1| build_step_1(0, 0, -1);
88| 1| build_step_2(0, 0, -1);
89| 500k| while (q--) {
------------------
| Branch (89:10): [True: 100.00%, False: 0.00%]
------------------
90| 500k| int u = rd.uh();
91| 500k| int v = rd.uh();
92| 500k| int k = rd.uh();
93| 500k| int w = lca(u, v);
94| 500k| int du = depth[u];
95| 500k| int dv = depth[v];
96| 500k| int dw = depth[w];
97| 500k| if (k <= du - dw) {
------------------
| Branch (97:9): [True: 5.03%, False: 94.97%]
------------------
98| 25.1k| int x = jump(u, du - k);
99| 25.1k| wt.uw(x);
100| 474k| } else if (k <= du + dv - dw - dw) {
------------------
| Branch (100:16): [True: 3.77%, False: 96.23%]
------------------
101| 17.9k| int x = jump(v, dw + dw - du + k);
102| 17.9k| wt.uw(x);
103| 456k| } else {
104| 456k| wt.puts(" -1", 3);
105| 456k| }
106| 500k| }
107| 1| return 0;
108| 1|}