/tmp/solutions/build/unionfind-main.cpp:
1| |#include <common.h>
2| |prelude;
3| |
4| |namespace {
5| |
6| |int pa[200000];
7| |
8| 98.9k|def find(int u) -> int {
9| 98.9k| int w = pa[u], v;
10| 98.9k| if (w < 0) return u;
^13.8k
------------------
| Branch (10:7): [True: 14.04%, False: 85.96%]
------------------
11| 89.5k| while (pa[w] >= 0) w = pa[w];
^85.0k ^4.52k
------------------
| Branch (11:10): [True: 5.05%, False: 94.95%]
------------------
12| 89.5k| while (pa[u] != w) v = u, u = pa[u], pa[v] = w;
^4.52k
------------------
| Branch (12:10): [True: 5.05%, False: 94.95%]
------------------
13| 85.0k| return w;
14| 98.9k|};
15| |
16| |} // namespace
17| |
18| 1|int main() {
19| 1| rd rd;
20| 1| wt wt;
21| 1| int n = rd.uh();
22| 1| int q = rd.uh();
23| 1| std::memset(pa, -1, 4 * n);
24| 49.4k| while (q--) {
------------------
| Branch (24:10): [True: 100.00%, False: 0.00%]
------------------
25| 49.4k| let t = rd.u1();
26| 49.4k| let u = find(rd.uh());
27| 49.4k| let v = find(rd.uh());
28| 49.4k| if (t == 0 && u != v) {
^24.9k
------------------
| Branch (28:9): [True: 50.39%, False: 49.61%]
| Branch (28:19): [True: 23.36%, False: 76.64%]
------------------
29| 5.82k| if (pa[u] < pa[v])
------------------
| Branch (29:11): [True: 34.56%, False: 65.44%]
------------------
30| 2.01k| pa[v] = u;
31| 3.81k| else if (pa[v] < pa[u])
------------------
| Branch (31:16): [True: 52.23%, False: 47.77%]
------------------
32| 1.99k| pa[u] = v;
33| 1.82k| else
34| 1.82k| pa[u] = v, --pa[v];
35| 5.82k| }
36| 49.4k| if (t == 1) {
------------------
| Branch (36:9): [True: 49.61%, False: 50.39%]
------------------
37| 24.5k| wt.u1(u == v);
38| 24.5k| }
39| 49.4k| }
40| 1| return 0;
41| 1|}