結果

問題 No.1054 Union add query
ユーザー hogeandfugahogeandfuga
提出日時 2021-04-25 15:07:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 981 ms / 2,000 ms
コード長 2,101 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 86,980 KB
実行使用メモリ 239,156 KB
最終ジャッジ日時 2023-09-17 14:05:19
合計ジャッジ時間 7,648 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 177 ms
80,256 KB
testcase_01 AC 174 ms
80,176 KB
testcase_02 AC 173 ms
80,128 KB
testcase_03 AC 839 ms
129,044 KB
testcase_04 AC 981 ms
239,156 KB
testcase_05 AC 771 ms
108,788 KB
testcase_06 AC 474 ms
160,916 KB
testcase_07 AC 425 ms
160,900 KB
testcase_08 AC 460 ms
160,580 KB
testcase_09 AC 575 ms
235,400 KB
testcase_10 AC 450 ms
233,212 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import Any


class WeightedUnionFind():

    T = Any

    def __init__(self, n: int) -> None:
        self.num = n
        self.rs = [1]*n
        self.ps = list(range(n))
        self.ws = [0]*n
        self.gs = [{i} for i in range(n)]

    def find(self, x: int) -> int:
        if x == self.ps[x]:
            return x
        else:
            t = self.find(self.ps[x])
            self.ws[x] += self.ws[self.ps[x]]
            self.ps[x] = t
            return self.ps[x]

    def weight(self, x: int) -> T:
        self.find(x)
        return self.ws[x]

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int, w: T) -> None:
        w += self.weight(x)
        w -= self.weight(y)
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rs[x] < self.rs[y]:
            x, y = y, x
            w = -w
        self.rs[x] += self.rs[y]
        self.ps[y] = x
        self.ws[y] = w
        self.gs[x].update(self.gs[y])
        self.num -= 1

    def diff(self, x: int, y: int) -> T:
        return self.weight(y) - self.weight(x)

    def size(self, x: int) -> int:
        return self.rs[self.find(x)]

    def count(self) -> int:
        return self.num

    def group(self, x: int) -> set:
        return self.gs[self.find(x)]


import sys
input = sys.stdin.buffer.readline


def main() -> None:
    N, Q = map(int, input().split())
    uf = WeightedUnionFind(N)
    vs = [0]*N

    def add(a: int, b: int) -> None:
        vs[uf.find(a)] += b

    def query(a: int) -> int:
        r = uf.find(a)
        return uf.diff(r, a) + vs[r]

    def unite(a: int, b: int) -> None:
        a = uf.find(a)
        b = uf.find(b)
        if a == b:
            return
        uf.unite(a, b, vs[b] - vs[a])

    for _ in range(Q):
        t, a, b = map(int, input().split())
        a -= 1
        if t == 1:
            b -= 1
            unite(a, b)
        if t == 2:
            add(a, b)
        if t == 3:
            print(query(a))


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