結果
問題 | No.2584 The University of Tree |
ユーザー | 👑 hitonanode |
提出日時 | 2023-12-12 00:59:58 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 378 ms / 3,000 ms |
コード長 | 2,634 bytes |
コンパイル時間 | 1,326 ms |
コンパイル使用メモリ | 102,708 KB |
実行使用メモリ | 58,820 KB |
最終ジャッジ日時 | 2023-12-12 01:00:11 |
合計ジャッジ時間 | 12,137 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 2 ms
6,676 KB |
testcase_07 | AC | 2 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 2 ms
6,676 KB |
testcase_10 | AC | 2 ms
6,676 KB |
testcase_11 | AC | 2 ms
6,676 KB |
testcase_12 | AC | 2 ms
6,676 KB |
testcase_13 | AC | 2 ms
6,676 KB |
testcase_14 | AC | 2 ms
6,676 KB |
testcase_15 | AC | 3 ms
6,676 KB |
testcase_16 | AC | 3 ms
6,676 KB |
testcase_17 | AC | 2 ms
6,676 KB |
testcase_18 | AC | 2 ms
6,676 KB |
testcase_19 | AC | 2 ms
6,676 KB |
testcase_20 | AC | 2 ms
6,676 KB |
testcase_21 | AC | 2 ms
6,676 KB |
testcase_22 | AC | 164 ms
31,104 KB |
testcase_23 | AC | 152 ms
14,828 KB |
testcase_24 | AC | 88 ms
8,960 KB |
testcase_25 | AC | 111 ms
9,984 KB |
testcase_26 | AC | 67 ms
10,496 KB |
testcase_27 | AC | 141 ms
17,920 KB |
testcase_28 | AC | 71 ms
14,336 KB |
testcase_29 | AC | 36 ms
8,320 KB |
testcase_30 | AC | 308 ms
26,536 KB |
testcase_31 | AC | 378 ms
40,660 KB |
testcase_32 | AC | 63 ms
15,616 KB |
testcase_33 | AC | 177 ms
57,836 KB |
testcase_34 | AC | 47 ms
7,676 KB |
testcase_35 | AC | 366 ms
39,364 KB |
testcase_36 | AC | 267 ms
22,044 KB |
testcase_37 | AC | 284 ms
18,244 KB |
testcase_38 | AC | 268 ms
18,244 KB |
testcase_39 | AC | 293 ms
27,432 KB |
testcase_40 | AC | 350 ms
40,316 KB |
testcase_41 | AC | 355 ms
34,500 KB |
testcase_42 | AC | 329 ms
35,908 KB |
testcase_43 | AC | 339 ms
30,788 KB |
testcase_44 | AC | 363 ms
47,428 KB |
testcase_45 | AC | 363 ms
47,428 KB |
testcase_46 | AC | 188 ms
58,820 KB |
testcase_47 | AC | 237 ms
21,952 KB |
testcase_48 | AC | 100 ms
9,216 KB |
testcase_49 | AC | 245 ms
17,040 KB |
testcase_50 | AC | 196 ms
14,780 KB |
testcase_51 | AC | 98 ms
9,984 KB |
testcase_52 | AC | 45 ms
6,676 KB |
ソースコード
#include <iostream> #include <utility> #include <vector> using namespace std; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define REP(i, n) FOR(i,0,n) #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vector<vector<int>> to_edges(N); vector<int> edgexor(N - 1); REP(i, N) { int C; cin >> C; while (C--) { int e; cin >> e; --e; edgexor.at(e) ^= i; to_edges.at(i).push_back(e); } } vector<mint> dpchild(N), dppar(N); vector<mint> ret(N); vector<int> curs(N, -1); auto rec1 = [&](auto &&self, int now, int prvvid, int prveid) -> void { if (prveid >= 0) { int cur = 0; while (to_edges.at(now).at(cur) != prveid) ++cur; curs.at(now) = cur; } const int D = to_edges.at(now).size(); for (int eid : to_edges.at(now)) { if (eid != prveid) self(self, edgexor.at(eid) ^ now, now, eid); } vector<mint> tmp; tmp.reserve((1 + D) * 2); tmp.push_back(1); for (int eid : to_edges.at(now)) tmp.push_back(dpchild.at(edgexor.at(eid) ^ now)); REP(i, 1 + D) tmp.push_back(tmp.at(i)); vector<mint> tmp_cs(tmp.size() + 1); const mint w = mint(now + 1).inv(); const mint winvpow = mint(now + 1).pow(D); REP(i, tmp.size()) tmp_cs.at(i + 1) = tmp_cs.at(i) * w + tmp.at(i); auto get_sum = [&](int l) -> mint { return tmp_cs.at(l + D) * winvpow - tmp_cs.at(l); }; ret.at(now) += get_sum(1); if (curs.at(now) >= 0) dpchild.at(now) += get_sum(1 + curs.at(now) + 1); REP(d, D) { int nxt = edgexor.at(to_edges.at(now).at(d)) ^ now; if (nxt != prvvid) dppar.at(nxt) += get_sum(1 + d + 1); } }; rec1(rec1, 0, -1, -1); auto rec2 = [&](auto &&self, int now, int prveid) -> void { const int D = to_edges.at(now).size(); ret.at(now) += dppar.at(now) * mint(now + 1).pow(1 + curs.at(now)); REP(d, D) { const int eid = to_edges.at(now).at(d); if (eid == prveid) continue; int nxt = edgexor.at(eid) ^ now; if (prveid >= 0) { dppar.at(nxt) += dppar.at(now) * mint(now + 1).pow((curs.at(now) + (D + 1) - d) % (D + 1)); } self(self, nxt, eid); } }; rec2(rec2, 0, -1); for (auto x : ret) cout << x.val() << '\n'; }