結果
問題 | No.1878 union-find の数え上げ |
ユーザー |
![]() |
提出日時 | 2022-03-18 22:11:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 577 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 96,780 KB |
最終ジャッジ日時 | 2024-10-03 09:41:39 |
合計ジャッジ時間 | 2,522 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 8 |
ソースコード
import sysinput = sys.stdin.readlineN = int(input())mod = 998244353e = [[] for _ in range(N + 1)]for x in range(2, N + 1):p = int(input())e[p].append(x)s = [1]vis = [0] * (N + 1)parent = [0] * (N + 1)vis[1] = 1order = []while len(s):x = s.pop()order.append(x)for y in e[x]:if vis[y]: continueparent[y] = xvis[y] = 1s.append(y)order.reverse()dp = [1] * (N + 1)for x in order:for y in e[x]:if parent[x] == y: continuedp[x] *= dp[y]dp[x] %= modif parent[x] > 1:dp[x] += 1dp[x] %= modprint(dp[1])