結果

問題 No.1878 union-find の数え上げ
ユーザー lam6er
提出日時 2025-03-20 20:59:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 851 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 93,852 KB
最終ジャッジ日時 2025-03-20 21:00:21
合計ジャッジ時間 6,522 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    if N == 1:
        print(1)
        return
    parent = [0] * (N + 1)  # parent[2] = p_2, etc.
    for i in range(2, N+1):
        parent[i] = int(sys.stdin.readline())
    
    # Compute depth of each node using BFS
    from collections import deque
    depth = [0] * (N + 1)
    visited = [False] * (N + 1)
    q = deque()
    q.append(1)
    visited[1] = True
    depth[1] = 0
    while q:
        u = q.popleft()
        for v in range(2, N+1):
            if parent[v] == u and not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                q.append(v)
    
    res = 1
    for i in range(2, N+1):
        res = res * depth[i] % MOD
    print(res)

if __name__ == '__main__':
    main()
0