src/ds/dsu/pd/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | class dsu_pd { | ||
| 8 | veci p; | ||
| 9 | vecp<u32, i32> edges; | ||
| 10 | |||
| 11 | public: | ||
| 12 | 28 | CEXPE dsu_pd(u32 sz) NE : p(sz, -1) {} | |
| 13 | |||
| 14 |
2/2✓ Branch 1 taken 3885430 times.
✓ Branch 2 taken 2439777 times.
|
6325207 | CEXP i32 find(u32 x) NE { retif_((p[x] < 0), (i32)x, find((u32)p[x])); } |
| 15 | ND CEXP u32 size() CNE { return (u32)p.size(); } | ||
| 16 | CEXP u32 size(u32 x) NE { return (u32)-p[(u32)find(x)]; } | ||
| 17 | 970993 | CEXP u32 time() NE { return (u32)edges.size(); } | |
| 18 | 971722 | CEXP bool same(u32 x, u32 y) NE { return find(x) == find(y); } | |
| 19 | 970993 | CEXP bool merge(u32 x, u32 y) NE { | |
| 20 |
2/2✓ Branch 2 taken 48258 times.
✓ Branch 3 taken 922735 times.
|
970993 | if ((x = (u32)find(x)) == (y = (u32)find(y))) return false; |
| 21 |
2/2✓ Branch 2 taken 197950 times.
✓ Branch 3 taken 724785 times.
|
922735 | if (p[x] > p[y]) swap(x, y); |
| 22 | 922735 | edges.emplace_back(y, p[y]), p[x] += p[y], p[y] = (i32)x; | |
| 23 | 922735 | return true; | |
| 24 | } | ||
| 25 | 970993 | CEXP void rollback(u32 t) NE { | |
| 26 |
2/2✓ Branch 1 taken 922735 times.
✓ Branch 2 taken 970993 times.
|
1893728 | while (edges.size() > t) { |
| 27 | 922735 | const auto [i, pi] = edges.back(); | |
| 28 | 922735 | edges.pop_back(); | |
| 29 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 922735 times.
|
922735 | assert(p[(u32)p[i]] < 0); |
| 30 | 922735 | p[(u32)p[i]] -= pi, p[i] = pi; | |
| 31 | } | ||
| 32 | 970993 | } | |
| 33 | }; | ||
| 34 | |||
| 35 | } // namespace tifa_libs | ||
| 36 |