test/cpv_local/graph/gomory_hu.bzoj2229.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/2229 | ||
| 2 | |||
| 3 | #include "../../../src/graph/ds/alist/lib.hpp" | ||
| 4 | #include "../../../src/graph/nf/gomory_hu/lib.hpp" | ||
| 5 | |||
| 6 | using namespace tifa_libs; | ||
| 7 | using std::cin, std::cout; | ||
| 8 | |||
| 9 | 15 | int main() { | |
| 10 | u32 t; | ||
| 11 |
1/2✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
|
15 | cin >> t; |
| 12 |
2/2✓ Branch 0 taken 91 times.
✓ Branch 1 taken 15 times.
|
106 | while (t--) { |
| 13 | u32 n, m; | ||
| 14 |
2/4✓ Branch 1 taken 91 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 91 times.
✗ Branch 5 not taken.
|
91 | cin >> n >> m; |
| 15 |
1/2✓ Branch 1 taken 91 times.
✗ Branch 2 not taken.
|
91 | vec<edge_t<u64>> edges(m); |
| 16 |
2/2✓ Branch 4 taken 140923 times.
✓ Branch 5 taken 91 times.
|
141014 | for (auto& [w, u, v] : edges) { |
| 17 |
3/6✓ Branch 1 taken 140923 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 140923 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 140923 times.
✗ Branch 8 not taken.
|
140923 | cin >> u >> v >> w; |
| 18 | 140923 | --u; | |
| 19 | 140923 | --v; | |
| 20 | } | ||
| 21 | 91 | alist<u64> mct(n); | |
| 22 |
2/4✓ Branch 2 taken 91 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 91 times.
✗ Branch 6 not taken.
|
91 | vvecuu mat(n, vecuu(n, std::numeric_limits<u64>::max())); |
| 23 |
2/2✓ Branch 5 taken 7480 times.
✓ Branch 6 taken 91 times.
|
7571 | for (auto mct_edges = gomory_hu(n, edges); auto&& [w, u, v] : mct_edges) { |
| 24 | 7480 | mct.add_arc(u, v, w); | |
| 25 | 7480 | mct.add_arc(v, u, w); | |
| 26 | 7480 | mat[u][v] = mat[v][u] = w; | |
| 27 | 91 | } | |
| 28 | 823273 | auto dfs = [&](auto&& dfs, u32 r, u32 u, u32 fa) -> void { | |
| 29 |
2/2✓ Branch 6 taken 1631404 times.
✓ Branch 7 taken 823273 times.
|
2454677 | for (auto [v, w] : mct[u]) |
| 30 |
4/6✓ Branch 0 taken 815702 times.
✓ Branch 1 taken 815702 times.
✓ Branch 7 taken 815702 times.
✗ Branch 8 not taken.
✓ Branch 12 taken 815702 times.
✗ Branch 13 not taken.
|
1631404 | if (v != fa) mat[r][v] = std::min({mat[r][v], mat[r][u], w}), dfs(dfs, r, v, u); |
| 31 | ; | ||
| 32 | 823273 | }; | |
| 33 |
2/2✓ Branch 0 taken 7571 times.
✓ Branch 1 taken 91 times.
|
7662 | flt_ (u32, r, 0, n) { |
| 34 |
1/2✓ Branch 2 taken 7571 times.
✗ Branch 3 not taken.
|
7571 | dfs(dfs, r, r, -1_u32); |
| 35 | 7571 | mat[r][r] = 0; | |
| 36 | } | ||
| 37 |
1/2✓ Branch 1 taken 91 times.
✗ Branch 2 not taken.
|
91 | map<u64, u32> cnts; |
| 38 |
2/2✓ Branch 0 taken 7571 times.
✓ Branch 1 taken 91 times.
|
7662 | flt_ (u32, i, 0, n) |
| 39 |
3/4✓ Branch 3 taken 407851 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 407851 times.
✓ Branch 6 taken 7571 times.
|
415422 | flt_ (u32, j, i + 1, n) ++cnts[mat[i][j]]; |
| 40 | u32 q; | ||
| 41 |
1/2✓ Branch 1 taken 91 times.
✗ Branch 2 not taken.
|
91 | cin >> q; |
| 42 |
2/2✓ Branch 0 taken 1198 times.
✓ Branch 1 taken 91 times.
|
1289 | for (u32 i = 0, x; i < q; ++i) { |
| 43 |
1/2✓ Branch 1 taken 1198 times.
✗ Branch 2 not taken.
|
1198 | cin >> x; |
| 44 | 1198 | u32 ans = 0; | |
| 45 |
4/6✓ Branch 1 taken 1198 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1198 times.
✗ Branch 5 not taken.
✓ Branch 10 taken 49584 times.
✓ Branch 11 taken 264 times.
|
49848 | for (auto&& [k, v] : cnts) { |
| 46 |
2/2✓ Branch 0 taken 934 times.
✓ Branch 1 taken 48650 times.
|
49584 | if (k > x) break; |
| 47 |
1/2✓ Branch 1 taken 48650 times.
✗ Branch 2 not taken.
|
48650 | ans += v; |
| 48 | } | ||
| 49 |
2/4✓ Branch 1 taken 1198 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1198 times.
✗ Branch 5 not taken.
|
1198 | cout << ans << '\n'; |
| 50 | } | ||
| 51 |
3/4✓ Branch 0 taken 76 times.
✓ Branch 1 taken 15 times.
✓ Branch 3 taken 76 times.
✗ Branch 4 not taken.
|
91 | if (t) cout << '\n'; |
| 52 | 91 | } | |
| 53 | 15 | } | |
| 54 |