/tmp/solutions/build/lca-fast.cpp:
1| |#include <common.h>
2| |#include <toy/bit.h>
3| |prelude;
4| |
5| |namespace {
6| |
7| |constexpr int N = 5e5;
8| |
9| |int parent[N];
10| |int node2id[N];
11| |int id2node[N];
12| |
13| |} // namespace
14| |
15| 25|int main() {
16| 25| rd rd;
17| 25| wt wt;
18| 25| int n = rd.uh();
19| 25| int q = rd.uh();
20| 25|#ifdef LOCAL
21| 25| std::memset(node2id, 0, 4 * n);
22| 25|#endif
23| 10.2M| for (int i = 1; i < n; ++i) parent[i] = rd.uh();
^10.2M^10.2M
------------------
| Branch (23:19): [True: 100.00%, False: 0.00%]
------------------
24| 10.2M| for (int i = n - 1; i > 0; --i) node2id[parent[i]] += node2id[i] + 1;
^10.2M^10.2M
------------------
| Branch (24:23): [True: 100.00%, False: 0.00%]
------------------
25| 10.2M| for (int i = 1; i < n; ++i) {
^10.2M
------------------
| Branch (25:19): [True: 100.00%, False: 0.00%]
------------------
26| 10.2M| int p = parent[i];
27| 10.2M| int &u = node2id[i];
28| 10.2M| int &w = node2id[p];
29| 10.2M| int t = w - u - 1;
30| 10.2M| u = w, w = t;
31| 10.2M| }
32| 10.2M| for (int i = 1; i < n; ++i) id2node[node2id[i]] = parent[i];
^10.2M^10.2M
------------------
| Branch (32:19): [True: 100.00%, False: 0.00%]
------------------
33| 25| int m = n / 64 + 1;
34| 25| int len = log(m) + 1;
35| 25| int table[len][m];
36| 25| int suf[n];
37| 25| int pre[n];
38| 10.2M| for (int min, i = 0; i < n; ++i) {
^10.2M
------------------
| Branch (38:24): [True: 100.00%, False: 0.00%]
------------------
39| 10.2M| int id = i & 63;
40| 10.2M| int value = pre[i] = id2node[i];
41| 10.2M| suf[i] = min = id ? std::min(min, value) : value;
^10.0M ^159k
------------------
| Branch (41:20): [True: 98.44%, False: 1.56%]
------------------
42| 10.2M| if (id == 63) table[0][i / 64] = suf[i];
^159k
------------------
| Branch (42:9): [True: 1.56%, False: 98.44%]
------------------
43| 10.2M| }
44| 10.2M| for (int min, i = n - 2; i >= 0; --i) {
^10.2M
------------------
| Branch (44:28): [True: 100.00%, False: 0.00%]
------------------
45| 10.2M| int id = ~i & 63;
46| 10.2M| int value = pre[i];
47| 10.2M| pre[i] = min = id ? std::min(min, value) : value;
^10.0M ^159k
------------------
| Branch (47:20): [True: 98.44%, False: 1.56%]
------------------
48| 10.2M| }
49| 307| for (int i = 1; i < len; ++i) {
^282
------------------
| Branch (49:19): [True: 91.86%, False: 8.14%]
------------------
50| 1.82M| for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
^1.82M
------------------
| Branch (50:39): [True: 99.98%, False: 0.02%]
------------------
51| 1.82M| table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
52| 1.82M| }
53| 282| }
54| 9.66M| while (q--) {
------------------
| Branch (54:10): [True: 100.00%, False: 0.00%]
------------------
55| 9.66M| int u = node2id[rd.uh()];
56| 9.66M| int v = node2id[rd.uh()];
57| 9.66M| int l = std::min(u, v) + 1;
58| 9.66M| int r = std::max(u, v);
59| 9.66M| int L = l / 64;
60| 9.66M| int R = r / 64;
61| 9.66M| int w;
62| 9.66M| if (L < R - 1) {
------------------
| Branch (62:9): [True: 99.94%, False: 0.06%]
------------------
63| 9.65M| int p = pre[l];
64| 9.65M| int s = suf[r];
65| 9.65M| w = std::min(p, s);
66| 9.65M| int k = log(R - L - 1);
67| 9.65M| int a = table[k][L + 1];
68| 9.65M| int b = table[k][R - (1 << k)];
69| 9.65M| int tmp = std::min(a, b);
70| 9.65M| w = std::min(w, tmp);
71| 9.65M| } else if (L == R - 1) {
^5.83k^5.83k
------------------
| Branch (71:16): [True: 66.83%, False: 33.17%]
------------------
72| 3.90k| int p = pre[l];
73| 3.90k| int s = suf[r];
74| 3.90k| w = std::min(p, s);
75| 3.90k| } else {
76| 1.93k| w = id2node[l];
77| 40.3k| for (int i = l + 1; i <= r; ++i) w = std::min(w, id2node[i]);
^38.3k^38.3k
------------------
| Branch (77:27): [True: 95.20%, False: 4.80%]
------------------
78| 1.93k| }
79| 9.66M| wt.uw(w);
80| 9.66M| }
81| 25| return 0;
82| 25|}