結果
問題 | No.1054 Union add query |
ユーザー | titia |
提出日時 | 2020-05-15 22:34:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,276 ms / 2,000 ms |
コード長 | 2,495 bytes |
コンパイル時間 | 650 ms |
コンパイル使用メモリ | 81,584 KB |
実行使用メモリ | 248,024 KB |
最終ジャッジ日時 | 2023-10-19 15:28:21 |
合計ジャッジ時間 | 10,130 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,392 KB |
testcase_01 | AC | 42 ms
53,392 KB |
testcase_02 | AC | 41 ms
53,392 KB |
testcase_03 | AC | 1,146 ms
158,424 KB |
testcase_04 | AC | 1,276 ms
248,024 KB |
testcase_05 | AC | 1,196 ms
144,604 KB |
testcase_06 | AC | 939 ms
178,140 KB |
testcase_07 | AC | 771 ms
177,952 KB |
testcase_08 | AC | 941 ms
178,064 KB |
testcase_09 | AC | 836 ms
237,068 KB |
testcase_10 | AC | 602 ms
237,712 KB |
ソースコード
import sys input = sys.stdin.readline N,Q=map(int,input().split()) Queries=[list(map(int,input().split())) for i in range(Q)] LIST=[[i] for i in range(N+1)] Group = [i for i in range(N+1)] # グループ分け Nodes = [1]*(N+1) # 各グループのノードの数 def find(x): while Group[x] != x: x=Group[x] return x def Union(x,y): if find(x) != find(y): if Nodes[find(x)] < Nodes[find(y)]: LIST[find(y)].extend(LIST[find(x)]) LIST[find(x)]=[] Nodes[find(y)] += Nodes[find(x)] Nodes[find(x)] = 0 Group[find(x)] = find(y) else: LIST[find(x)].extend(LIST[find(y)]) LIST[find(y)]=[] Nodes[find(x)] += Nodes[find(y)] Nodes[find(y)] = 0 Group[find(y)] = find(x) for t,a,b in Queries: if t==1: Union(a,b) X=[0] for i in range(1,N+1): X.extend(LIST[i]) X_INV=[-1]*(N+1) for ind,x in enumerate(X): X_INV[x]=ind Group = [i for i in range(N+1)] # グループ分け Nodes = [1]*(N+1) # 各グループのノードの数 Last = [i for i in range(N+1)] def find(x): while Group[x] != x: x=Group[x] return x def Union(x,y): if find(x) != find(y): if Nodes[find(x)] < Nodes[find(y)]: Last[find(y)]=Last[find(x)] Nodes[find(y)] += Nodes[find(x)] Nodes[find(x)] = 0 Group[find(x)] = find(y) else: Last[find(x)]=Last[find(y)] Nodes[find(x)] += Nodes[find(y)] Nodes[find(y)] = 0 Group[find(y)] = find(x) LEN=N+1 # 必要なら座標圧縮する seg_el=1<<((N+1).bit_length()) # Segment treeの台の要素数 SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化 def getvalue(n,seg_el): # 一点の値を取得 i=n+seg_el ANS=0 ANS=SEG[i] i>>=1# 子ノードへ while i!=0: ANS+=SEG[i] i>>=1 return ANS def updates(l,r,x): # 区間[l,r)のminを更新. L=l+seg_el R=r+seg_el while L<R: if L & 1: SEG[L]+=x L+=1 if R & 1: R-=1 SEG[R]+=x L>>=1 R>>=1 for t,a,b in Queries: if t==1: Union(a,b) elif t==2: updates(X_INV[find(a)],X_INV[Last[find(a)]]+1,b) else: print(getvalue(X_INV[a],seg_el))