GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 44 / 0 / 44
Functions: 100.0% 4 / 0 / 4
Branches: 74.3% 52 / 0 / 70
test/cpv_local/graph/best_theorem.bzoj3659m.cpp
Line Branch Exec Source
1 // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/3659m
2
3 #include "../../../src/fast/rsort32/lib.hpp"
4 #include "../../../src/graph/ds/alist/lib.hpp"
5 #include "../../../src/graph/ds/amat/lib.hpp"
6 #include "../../../src/graph/ds/info/lib.hpp"
7 #include "../../../src/graph/euler_trail/lib.hpp"
8 #include "../../../src/graph/kirchhoff/lib.hpp"
9 #include "../../../src/lalg/mat/ge/lib.hpp"
10 #include "../../../src/math/ds/mint/ms/lib.hpp"
11
12 using namespace tifa_libs;
13 using std::cin, std::cout;
14 using mint = mint_ms<1'000'003>;
15 vec<mint> fact(200'005);
16
17 11 int main() {
18 11 fact[0] = 1;
19
2/2
✓ Branch 5 taken 2200044 times.
✓ Branch 6 taken 11 times.
 2200055 flt_ (u32, i, 1, (u32)fact.size()) fact[i] = fact[i - 1] * i;
20
21 u32 t;
22
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 cin >> t;
23
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 11 times.
 53 while (t--) {
24 u32 n;
25
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 cin >> n;
26 42 alist<void, degin_tag, degout_tag, arc_cnt_tag> g(n);
27
2/2
✓ Branch 0 taken 1373 times.
✓ Branch 1 taken 42 times.
 1415 for (u32 i = 0, s; i < n; ++i) {
28
1/2
✓ Branch 1 taken 1373 times.
✗ Branch 2 not taken.
 1373 cin >> s;
29
3/4
✓ Branch 1 taken 9110623 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9110623 times.
✓ Branch 5 taken 1373 times.
 9111996 for (u32 j = 0, x; j < s; ++j) (cin >> x), g.add_arc(i, x - 1);
30 }
31
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 41 times.
 42 if (!g.esize()) {
32
1/2
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
 1 cout << "1\n";
33 1 continue;
34 }
35
6/6
✓ Branch 1 taken 34 times.
✓ Branch 2 taken 7 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 9 times.
✓ Branch 7 taken 32 times.
 41 if (!is_eulerian(g) || !g.dout[0]) {
36
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 cout << "0\n";
37 9 continue;
38 }
39
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 vecb vis(n);
40 1326 auto f = [&](auto&& f, u32 x) -> void {
41
2/2
✓ Branch 6 taken 9110581 times.
✓ Branch 7 taken 1326 times.
 9111907 for (auto v : g[x])
42
5/8
✓ Branch 2 taken 9110581 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1294 times.
✓ Branch 6 taken 9109287 times.
✓ Branch 9 taken 1294 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 1294 times.
✗ Branch 15 not taken.
 9110581 if (!vis[v]) vis[v] = 1, f(f, v);
43 1326 };
44
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 32 times.
✗ Branch 6 not taken.
 32 vis[0] = 1, f(f, 0);
45
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 vecu ids(n, -1_u32), inv_ids;
46 32 u32 cnt_ids = 0;
47
2/2
✓ Branch 0 taken 1338 times.
✓ Branch 1 taken 32 times.
 1370 flt_ (u32, i, 0, n)
48
4/6
✓ Branch 1 taken 1338 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1326 times.
✓ Branch 5 taken 12 times.
✓ Branch 8 taken 1326 times.
✗ Branch 9 not taken.
 1338 if (vis[i]) ids[i] = cnt_ids++, inv_ids.push_back(i);
49 32 amat<mint> mat(cnt_ids);
50
2/2
✓ Branch 0 taken 1326 times.
✓ Branch 1 taken 32 times.
 1358 flt_ (u32, id, 0, cnt_ids) {
51 1326 auto& tos = g[inv_ids[id]];
52
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1326 times.
 1326 if (tos.empty()) continue;
53 1326 ::sort(tos);
54 1326 u32 cnt = 1, pre = tos[0];
55
2/2
✓ Branch 1 taken 9109255 times.
✓ Branch 2 taken 1326 times.
 9110581 flt_ (u32, j, 1, (u32)tos.size())
56
2/2
✓ Branch 2 taken 102239 times.
✓ Branch 3 taken 9007016 times.
 9109255 if (tos[j] != pre) {
57 102239 mat.add_arc(id, ids[pre], cnt), pre = tos[j], cnt = 1;
58 9007016 } else ++cnt;
59 1326 mat.add_arc(id, ids[pre], cnt);
60 }
61 232480 auto is_0 = [](cT_(mint) x) { return x.val() == 0; };
62 32 auto ge = [&](matrix<mint>& A, bool clear_u) { return ge_mat<mint, decltype(is_0), true>(A, is_0, clear_u); };
63
1/2
✓ Branch 5 taken 32 times.
✗ Branch 6 not taken.
 32 mint ans = kirchhoff<true>(mat, ids[0], ge) * fact[g.dout[inv_ids[0]]];
64
2/2
✓ Branch 4 taken 1294 times.
✓ Branch 5 taken 32 times.
 1326 flt_ (u32, i, 1, cnt_ids) ans *= fact[g.dout[inv_ids[i]] - 1];
65
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 cout << ans << '\n';
66
2/2
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 10 times.
 42 }
67 11 }
68