結果

問題 No.1054 Union add query
コンテスト
ユーザー qib
提出日時 2023-01-29 03:00:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 904 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 151,908 KB
最終ジャッジ日時 2024-06-29 02:52:06
合計ジャッジ時間 5,581 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

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