test/cpv/library-checker-datastructure/unionfind_with_potential_non_commutative_group.mints-ms.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #define AUTO_GENERATED | ||
| 2 | // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind_with_potential_non_commutative_group | ||
| 3 | #include "../../../src/ds/dsu/w/lib.hpp" | ||
| 4 | #include "../../../src/io/container/lib.hpp" | ||
| 5 | #include "../../../src/lalg/ds/mat/lib.hpp" | ||
| 6 | |||
| 7 | using namespace tifa_libs; | ||
| 8 | CEXP u32 MOD = 998244353; | ||
| 9 | |||
| 10 | #include "../../../src/math/ds/mint/ms/lib.hpp" | ||
| 11 | |||
| 12 | using namespace tifa_libs; | ||
| 13 | using mint = mint_ms<MOD>; | ||
| 14 | using mat = tifa_libs::matrix<mint>; | ||
| 15 | |||
| 16 | 2316601 | auto inv(mat CR m) { // ensure det(m)==1 | |
| 17 |
3/6✓ Branch 4 taken 2316601 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 4633202 times.
✓ Branch 9 taken 2316601 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
|
16216207 | return mat({{m(1, 1), -m(0, 1)}, {-m(1, 0), m(0, 0)}}); |
| 18 |
2/8✓ Branch 3 taken 2316601 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 2316601 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
|
11583005 | } |
| 19 | 7407635 | auto op(mat CR x, mat CR y) { return x * y; } | |
| 20 | |||
| 21 | 18 | int main() { | |
| 22 |
1/2✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
|
18 | std::cin.tie(nullptr)->std::ios::sync_with_stdio(false); |
| 23 | u32 n, q; | ||
| 24 |
2/4✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
|
18 | std::cin >> n >> q; |
| 25 |
3/6✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 36 times.
✓ Branch 8 taken 18 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
72 | tifa_libs::dsu_weighted<mat, op, inv> dsu(n, mat({{1, 0}, {0, 1}})); |
| 26 |
2/2✓ Branch 0 taken 2448339 times.
✓ Branch 1 taken 18 times.
|
2448357 | flt_ (u32, i, 0, q) { |
| 27 | u32 op, u, v; | ||
| 28 |
3/6✓ Branch 1 taken 2448339 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2448339 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2448339 times.
✗ Branch 8 not taken.
|
2448339 | std::cin >> op >> u >> v; |
| 29 |
2/2✓ Branch 0 taken 956803 times.
✓ Branch 1 taken 1491536 times.
|
2448339 | if (op) { |
| 30 |
3/4✓ Branch 1 taken 666244 times.
✓ Branch 2 taken 290559 times.
✓ Branch 4 taken 666244 times.
✗ Branch 5 not taken.
|
956803 | if (!dsu.same(u, v)) std::cout << "-1\n"; |
| 31 |
1/2✓ Branch 4 taken 290559 times.
✗ Branch 5 not taken.
|
290559 | else std::cout << dsu.diff(u, v).data() << '\n'; |
| 32 | } else { | ||
| 33 | 1491536 | mat k(2, 2); | |
| 34 | 1491536 | std::cin >> k; | |
| 35 |
3/6✓ Branch 1 taken 1491536 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1491536 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1491536 times.
✗ Branch 9 not taken.
|
1491536 | std::cout << dsu.merge(u, v, k) << '\n'; |
| 36 | 1491536 | } | |
| 37 | } | ||
| 38 | 18 | return 0; | |
| 39 |
2/8✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
|
72 | } |
| 40 |