test/cpv/library-checker-tree/vertex_set_path_composite.mints-bs.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #define AUTO_GENERATED | ||
| 2 | // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/vertex_set_path_composite/ | ||
| 3 | #include "../../../src/graph/ds/alist/lib.hpp" | ||
| 4 | #include "../../../src/tree/hld/lib.hpp" | ||
| 5 | #include "../../../src/tree/lca_hld/lib.hpp" | ||
| 6 | |||
| 7 | using namespace tifa_libs; | ||
| 8 | CEXP u32 MOD = 998244353; | ||
| 9 | |||
| 10 | #include "../../../src/math/ds/mint/bs/lib.hpp" | ||
| 11 | |||
| 12 | using namespace tifa_libs; | ||
| 13 | using mint = mint_bs<MOD>; | ||
| 14 | using Ty = mint; | ||
| 15 | using T = std::pair<Ty, Ty>; | ||
| 16 | using F = T; | ||
| 17 | using tree_t = tree<alist<>>; | ||
| 18 | |||
| 19 | 139964550 | CEXP auto op_ab(T a, T b) { // a(b(x)) | |
| 20 | 139964550 | return T{a.first * b.first, a.first * b.second + a.second}; | |
| 21 | } | ||
| 22 | 77792454 | CEXP auto op_ba(T a, T b) { // b(a(x)) | |
| 23 | 77792454 | return op_ab(b, a); | |
| 24 | } | ||
| 25 | 40 | CEXP auto e() { return T{1, 0}; } | |
| 26 | 40 | CEXP auto id() { return F{1, 0}; } | |
| 27 | 1861712 | CEXP void mapping(T& x, F a) { x = a; } | |
| 28 | ✗ | CEXP void composition(F& x, F) { x = F{1, 0}; } | |
| 29 | |||
| 30 | 20 | int main() { | |
| 31 |
1/2✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
|
20 | std::cin.tie(nullptr)->std::ios::sync_with_stdio(false); |
| 32 | u32 n, q; | ||
| 33 |
2/4✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
|
20 | std::cin >> n >> q; |
| 34 |
1/2✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
|
20 | vec<T> a(n); |
| 35 |
2/2✓ Branch 7 taken 2334317 times.
✓ Branch 8 taken 20 times.
|
2334337 | for (auto& x : a) std::cin >> x.first >> x.second; |
| 36 | 20 | tree_t tr(n); | |
| 37 |
4/6✓ Branch 1 taken 2334297 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2334297 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 2334297 times.
✓ Branch 9 taken 20 times.
|
2334317 | for (u32 i = 1, u, v; i < n; ++i) std::cin >> u >> v, tr.add_arc(u, v), tr.add_arc(v, u); |
| 38 |
1/2✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
|
20 | tifa_libs::lca_hld lca(tr); |
| 39 | 20 | tifa_libs::hld<tree_t, T, op_ba, F, mapping, composition> hld(e(), id(), tr, lca.info, a); | |
| 40 | 20 | tifa_libs::hld<tree_t, T, op_ab, F, mapping, composition> hld1(e(), id(), tr, lca.info, a); | |
| 41 |
2/2✓ Branch 0 taken 2423828 times.
✓ Branch 1 taken 20 times.
|
2423848 | for (u32 i = 0, opt; i < q; ++i) { |
| 42 |
1/2✓ Branch 1 taken 2423828 times.
✗ Branch 2 not taken.
|
2423828 | std::cin >> opt; |
| 43 |
2/2✓ Branch 0 taken 930856 times.
✓ Branch 1 taken 1492972 times.
|
2423828 | if (opt == 0) { |
| 44 | u32 x; | ||
| 45 | 930856 | Ty y, z; | |
| 46 |
1/2✓ Branch 1 taken 930856 times.
✗ Branch 2 not taken.
|
930856 | std::cin >> x >> y >> z; |
| 47 | 930856 | hld.node_update(x, F(y, z)), hld1.node_update(x, F(y, z)); | |
| 48 | } else { | ||
| 49 | u32 x, y; | ||
| 50 | 1492972 | Ty z; | |
| 51 |
2/4✓ Branch 1 taken 1492972 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1492972 times.
✗ Branch 5 not taken.
|
1492972 | std::cin >> x >> y >> z; |
| 52 | 1492972 | auto [retu, retv] = lca.getchain(x, y); | |
| 53 | 1492972 | T ret1 = e(), ret2 = e(); | |
| 54 |
2/2✓ Branch 8 taken 6556543 times.
✓ Branch 9 taken 1492972 times.
|
8049515 | for (auto x : retu) ret1 = op_ba(ret1, hld1.chain_query(x.first, x.second)); |
| 55 |
2/2✓ Branch 8 taken 6062461 times.
✓ Branch 9 taken 1492972 times.
|
7555433 | for (auto x : retv) ret2 = op_ba(ret2, hld.chain_query(x.first, x.second)); |
| 56 | 1492972 | ret1 = op_ba(ret1, ret2); | |
| 57 |
1/2✓ Branch 4 taken 1492972 times.
✗ Branch 5 not taken.
|
1492972 | std::cout << ret1.first * z + ret1.second << '\n'; |
| 58 | 1492972 | } | |
| 59 | } | ||
| 60 | 20 | return 0; | |
| 61 | 20 | } | |
| 62 |