GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 42 / 0 / 42
Functions: 100.0% 4 / 0 / 4
Branches: 66.7% 40 / 0 / 60
test/cpv/library-checker-graph/counting_eulerian_circuits.mintd-bd.cpp
Line Branch Exec Source
1 #define AUTO_GENERATED
2 // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/counting_eulerian_circuits/
3 #include "../../../src/comb/seq/fact/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
11 using namespace tifa_libs;
12 CEXP u32 MOD = 998244353;
13
14 #include "../../../src/math/ds/mint/bd/lib.hpp"
15
16 using namespace tifa_libs;
17 using mint = mint_bd<__LINE__>;
18
19 16 int main() {
20 16 mint::set_mod(MOD);
21
1/2
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 16 std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
22 u32 n, m;
23
2/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
 16 std::cin >> n >> m;
24 16 auto fact = gen_fact<mint>(m + 1);
25 16 alist<void, degin_tag, degout_tag, arc_cnt_tag> g(n);
26 16 u32 start = 0;
27
2/2
✓ Branch 0 taken 2400022 times.
✓ Branch 1 taken 16 times.
 2400038 for (u32 i = 0, u, v; i < m; ++i) {
28
2/4
✓ Branch 1 taken 2400022 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2400022 times.
✗ Branch 5 not taken.
 2400022 std::cin >> u >> v;
29 2400022 g.add_arc(u, v);
30 2400022 start = u;
31 }
32
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 11 times.
 16 if (!is_eulerian(g)) {
33
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 std::cout << "0\n";
34 5 return 0;
35 }
36
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 vecb vis(n);
37 2668 auto f = [&](auto&& f, u32 x) -> void {
38
2/2
✓ Branch 6 taken 1600020 times.
✓ Branch 7 taken 2668 times.
 1602688 for (auto v : g[x])
39
5/8
✓ Branch 2 taken 1600020 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2657 times.
✓ Branch 6 taken 1597363 times.
✓ Branch 9 taken 2657 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 2657 times.
✗ Branch 15 not taken.
 1600020 if (!vis[v]) vis[v] = 1, f(f, v);
40 2668 };
41
2/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 11 times.
✗ Branch 6 not taken.
 11 vis[start] = 1, f(f, start);
42
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 11 vecu ids(n, -1_u32), inv_ids;
43 11 u32 cnt_ids = 0;
44
2/2
✓ Branch 0 taken 4017 times.
✓ Branch 1 taken 11 times.
 4028 flt_ (u32, i, 0, n)
45
4/6
✓ Branch 1 taken 4017 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2668 times.
✓ Branch 5 taken 1349 times.
✓ Branch 8 taken 2668 times.
✗ Branch 9 not taken.
 4017 if (vis[i]) ids[i] = cnt_ids++, inv_ids.push_back(i);
46 11 amat<mint> mat(cnt_ids);
47
2/2
✓ Branch 0 taken 2668 times.
✓ Branch 1 taken 11 times.
 2679 flt_ (u32, id, 0, cnt_ids) {
48 2668 auto& tos = g[inv_ids[id]];
49
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2668 times.
 2668 if (tos.empty()) continue;
50
1/2
✓ Branch 1 taken 2668 times.
✗ Branch 2 not taken.
 2668 tifa_libs::sort(tos);
51 2668 u32 cnt = 1, pre = tos[0];
52
2/2
✓ Branch 1 taken 1597352 times.
✓ Branch 2 taken 2668 times.
 1600020 flt_ (u32, j, 1, (u32)tos.size())
53
2/2
✓ Branch 2 taken 664087 times.
✓ Branch 3 taken 933265 times.
 1597352 if (tos[j] != pre) mat.add_arc(id, ids[pre], cnt), pre = tos[j], cnt = 1;
54 933265 else ++cnt;
55 2668 mat.add_arc(id, ids[pre], cnt);
56 }
57 2261498 auto is_0 = [](cT_(mint) x) { return x.val() == 0; };
58 10 auto ge = [&](matrix<mint>& A, bool clear_u) { return ge_mat<mint, decltype(is_0), true>(A, is_0, clear_u); };
59
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 11 mint ans = kirchhoff<true>(mat, ids[start], ge);
60
2/2
✓ Branch 0 taken 2668 times.
✓ Branch 1 taken 11 times.
 2679 flt_ (u32, i, 0, cnt_ids)
61
1/2
✓ Branch 2 taken 2668 times.
✗ Branch 3 not taken.
 2668 if (g.dout[inv_ids[i]]) ans *= fact[g.dout[inv_ids[i]] - 1];
62
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 11 std::cout << ans << '\n';
63 11 return 0;
64 16 }
65