結果

問題 No.1054 Union add query
ユーザー lam6er
提出日時 2025-03-20 20:23:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 497 ms / 2,000 ms
コード長 1,541 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 266,080 KB
最終ジャッジ日時 2025-03-20 20:25:32
合計ジャッジ時間 5,288 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))  # 1-based indexing
        self.delta = [0] * (n + 1)
        self.add = [0] * (n + 1)
        self.rank = [1] * (n + 1)
    
    def find(self, u):
        path = []
        while self.parent[u] != u:
            path.append(u)
            u = self.parent[u]
        # Path compression
        acc = 0
        for v in reversed(path):
            self.parent[v] = u
            acc += self.delta[v]
            self.delta[v] = acc
        return u
    
    def union(self, a, b):
        rx = self.find(a)
        ry = self.find(b)
        if rx == ry:
            return
        # Union by rank
        if self.rank[rx] > self.rank[ry]:
            rx, ry = ry, rx
        self.parent[rx] = ry
        self.delta[rx] = self.add[rx] - self.add[ry]
        if self.rank[rx] == self.rank[ry]:
            self.rank[ry] += 1

def main():
    data = list(map(int, sys.stdin.read().split()))
    ptr = 0
    n = data[ptr]
    ptr += 1
    q = data[ptr]
    ptr += 1
    uf = UnionFind(n)
    output = []
    for _ in range(q):
        t = data[ptr]
        a = data[ptr + 1]
        b = data[ptr + 2]
        ptr += 3
        if t == 1:
            uf.union(a, b)
        elif t == 2:
            root = uf.find(a)
            uf.add[root] += b
        else:  # t == 3
            root = uf.find(a)
            ans = uf.delta[a] + uf.add[root]
            output.append(str(ans))
    print('\n'.join(output))

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