Test/AtCoder/arc197_d.test.cpp

View this file on GitHub
Last update: 2025-05-05 21:42:21+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://atcoder.jp/contests/arc197/submissions/65531577
Link: https://atcoder.jp/contests/arc197/tasks/arc197_d

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/arc197/tasks/arc197_d"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Regular Contest 197 (Div. 2) D - Ancestor Relation
 * https://atcoder.jp/contests/arc197/submissions/65531577
 */

#include "../../Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
#include "atcoder/modint"
using namespace zawa;
using mint = atcoder::modint998244353;

#include <iostream>
#include <ranges>
int N, A[400][400];
mint solve(std::vector<int> a) {
    if (a.empty()) return 1;
    std::vector<bool> all(N);
    for (int v : a) {
        all[v] = true;
        for (int x : a) if (A[v][x] == 0) all[v] = false;
    }
    if (a[0] == 0 and !all[0]) return 0;
    int cnt = std::ranges::count(all, true);
    if (cnt == 0) return 0;
    if (a[0] == 0) cnt--;
    DisjointSetUnion dsu(N);
    for (int v : a) if (!all[v]) for (int x : a) if (!all[x]) {
        if (A[v][x]) dsu.merge(v, x);
    }
    auto gs = dsu.enumerate<int>();
    mint res = 1;
    for (int i = 1 ; i <= cnt ; i++) res *= mint::raw(i);
    std::vector<bool> next(N);
    for (int v : a) if (!all[v]) next[v] = true;
    for (const std::vector<int>& g : gs) if (next[g[0]]) {
        res *= solve(g);
    }
    return res;
}
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> N;
        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < N ; j++) std::cin >> A[i][j];
        }
        std::vector<int> a(N);
        std::iota(a.begin(), a.end(), 0);
        std::cout << solve(a).val() << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header