結果

問題 No.1451 集団登校
ユーザー gew1fw
提出日時 2025-06-12 16:02:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 292 ms / 2,000 ms
コード長 1,744 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 162,736 KB
最終ジャッジ日時 2025-06-12 16:02:15
合計ジャッジ時間 6,184 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 10**9 + 7

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    parents = list(range(N + 1))  # 1-based indexing
    size = [1] * (N + 1)
    prob = [defaultdict(int) for _ in range(N + 1)]
    for i in range(1, N + 1):
        prob[i][i] = 1

    def find(u):
        while parents[u] != u:
            parents[u] = parents[parents[u]]
            u = parents[u]
        return u

    inv2 = pow(2, MOD - 2, MOD)

    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        ra = find(a)
        rb = find(b)
        if ra == rb:
            continue
        sa = size[ra]
        sb = size[rb]
        if sa > sb:
            # Merge rb into ra
            parents[rb] = ra
            size[ra] += size[rb]
        elif sb > sa:
            # Merge ra into rb
            parents[ra] = rb
            size[rb] += size[ra]
        else:
            # Merge into ra, equal size
            new_prob = defaultdict(int)
            # Add contributions from ra and rb, each multiplied by inv2
            for k, v in prob[ra].items():
                new_prob[k] = (new_prob[k] + v * inv2) % MOD
            for k, v in prob[rb].items():
                new_prob[k] = (new_prob[k] + v * inv2) % MOD
            # Update ra's prob
            prob[ra] = new_prob
            # Update size and parent
            size[ra] += size[rb]
            parents[rb] = ra

    # After all operations, collect the result
    res = [0] * (N + 1)
    for i in range(1, N + 1):
        root = find(i)
        res[i] = prob[root].get(i, 0) % MOD

    for i in range(1, N + 1):
        print(res[i])

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