結果
問題 | No.1878 union-find の数え上げ |
ユーザー |
|
提出日時 | 2023-03-10 21:39:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 1,085 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 81,916 KB |
実行使用メモリ | 104,028 KB |
最終ジャッジ日時 | 2024-09-18 03:53:04 |
合計ジャッジ時間 | 3,120 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 |
ソースコード
def oi(): return int(input())def os(): return input()def mi(): return list(map(int, input().split()))# import sys# input = sys.stdin.readline# import sys# sys.setrecursionlimit(10**8)# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')input_count = 0mod = 998244353input_count = 0N = oi()NODE = NLOOP_NUM = N-1maps = {i:[] for i in range(NODE)}num = 2for i in range(LOOP_NUM):parent = oi()maps[num-1].append(parent-1)maps[parent-1].append(num-1)num += 1from collections import dequereached = [-1] * N ## 1つ前のノードを持たせると微妙に遅くなるのでやめようdeq = deque([[0,0]])while deq:node, num = deq.popleft() #BFSreached[node] = numfor next_node in maps[node]:# 訪問済み判定if reached[next_node] != -1:continuereached[next_node] = num+1deq.append([next_node,num+1])out = 1from collections import Counterfor k, v in Counter(reached).items():if k==0:continueout = (out * pow(k, v, mod))%modprint(out)