結果

問題 No.1054 Union add query
ユーザー qibqib
提出日時 2023-01-29 03:00:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 904 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 87,216 KB
実行使用メモリ 151,180 KB
最終ジャッジ日時 2023-09-11 12:26:18
合計ジャッジ時間 7,211 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,392 KB
testcase_01 AC 72 ms
71,488 KB
testcase_02 AC 72 ms
71,320 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, q = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(q)]

par = [i for i in range(n)]
grp = [[i] for i in range(n)]
ans = [0 for _ in range(n)]
order = [0 for _ in range(n)]
for t, a, b in queries:
  if t == 1:
    a = par[a - 1]
    b = par[b - 1]
    if a == b:
      continue

    la = len(grp[a])
    lb = len(grp[b])
    if la < lb:
      a, b = b, a
      la, lb = lb, la

    if order[a] != 0:
      for v in grp[a]:
        ans[v] += order[a]
      order[a] = 0

    if order[b] != 0:
      for v in grp[b]:
        ans[v] += order[b]
      order[b] = 0

    while len(grp[b]) > 0:
      cur = grp[b].pop()
      grp[a].append(cur)
      par[cur] = a
  elif t == 2:
    a = par[a - 1]
    order[a] += b
  elif t == 3:
    a -= 1
    ra = par[a]
    if order[ra] != 0:
      for v in grp[ra]:
        ans[v] += order[ra]
      order[ra] = 0

    print(ans[a])
0