test/cpv_local/tree/virtual_tree.bzoj2286.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/2286 | ||
| 2 | |||
| 3 | #include "../../../src/graph/ds/alist/lib.hpp" | ||
| 4 | #include "../../../src/io/fastin/lib.hpp" | ||
| 5 | #include "../../../src/io/fastout/lib.hpp" | ||
| 6 | #include "../../../src/tree/virtual_tree/lib.hpp" | ||
| 7 | |||
| 8 | using namespace tifa_libs; | ||
| 9 | 10 | int main() { | |
| 10 | u32 n; | ||
| 11 | 10 | fin_uint >> n; | |
| 12 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
30 | vecu sign(n), min_(n); |
| 13 | using Tw = u32; | ||
| 14 | using tree_t = tree<alist<Tw>>; | ||
| 15 | 10 | tree_t trw(n); | |
| 16 |
2/2✓ Branch 5 taken 1502100 times.
✓ Branch 6 taken 10 times.
|
1502110 | for (u32 i = 1, u, v, w; i < n; ++i) fin_uint >> u >> v >> w, --u, --v, trw.add_arc(u, v, w), trw.add_arc(v, u, w); |
| 17 | 1502110 | auto dfs = [&](auto&& dfs, u32 u, u32 fa, u32 min__) -> void { | |
| 18 | 1502110 | min_[u] = min__; | |
| 19 |
2/2✓ Branch 6 taken 3004200 times.
✓ Branch 7 taken 1502110 times.
|
4506310 | for (auto [to, w] : trw[u]) |
| 20 |
3/4✓ Branch 0 taken 1502100 times.
✓ Branch 1 taken 1502100 times.
✓ Branch 4 taken 1502100 times.
✗ Branch 5 not taken.
|
3004200 | if (to != fa) dfs(dfs, to, u, std::min(min__, w)); |
| 21 | 1502110 | }; | |
| 22 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | dfs(dfs, 0, 0, INT32_MAX); |
| 23 | 10 | virtual_tree vt(trw); | |
| 24 | u32 m, k; | ||
| 25 | 10 | fin_uint >> m; | |
| 26 |
2/2✓ Branch 0 taken 560676 times.
✓ Branch 1 taken 10 times.
|
560686 | flt_ (u32, i, 0, m) { |
| 27 | 560676 | fin_uint >> k; | |
| 28 |
1/2✓ Branch 1 taken 560676 times.
✗ Branch 2 not taken.
|
560676 | vecu a(k); |
| 29 |
2/2✓ Branch 7 taken 3833872 times.
✓ Branch 8 taken 560676 times.
|
4394548 | for (auto& x : a) fin_uint >> x, --x, sign[x] = 1; |
| 30 | 560676 | vt.build(a); | |
| 31 | 6036203 | auto dp = [&](auto&& dp, u32 u) -> u64 { | |
| 32 |
2/2✓ Branch 1 taken 3564015 times.
✓ Branch 2 taken 2472188 times.
|
6036203 | if (sign[u]) return min_[u]; |
| 33 | 2472188 | u64 ret = 0; | |
| 34 |
3/4✓ Branch 6 taken 5475527 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 5475527 times.
✓ Branch 11 taken 2472188 times.
|
7947715 | for (auto to : vt.vt[u]) ret += dp(dp, to); |
| 35 |
2/2✓ Branch 0 taken 1911512 times.
✓ Branch 1 taken 560676 times.
|
2472188 | retif_((u), std::min(u64(min_[u]), ret), ret); |
| 36 | 560676 | }; | |
| 37 |
1/2✓ Branch 1 taken 560676 times.
✗ Branch 2 not taken.
|
560676 | fout << dp(dp, 0) << '\n'; |
| 38 |
2/2✓ Branch 2 taken 3833872 times.
✓ Branch 3 taken 560676 times.
|
4394548 | flt_ (u32, i, 0, k) sign[a[i]] = 0; |
| 39 | 560676 | } | |
| 40 | 10 | } | |
| 41 |