結果
問題 | No.1054 Union add query |
ユーザー |
![]() |
提出日時 | 2020-05-15 22:43:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 895 ms / 2,000 ms |
コード長 | 1,733 bytes |
コンパイル時間 | 766 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 211,524 KB |
最終ジャッジ日時 | 2024-09-19 11:54:39 |
合計ジャッジ時間 | 7,277 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
import sysinput = lambda: sys.stdin.readline().rstrip()N, Q = map(int, input().split())P = [-1 for i in range(N)]LA = [i for i in range(N)]NE = [-1] * Ndef par(a):L = []while P[a] >= 0:L.append(a)a = P[a]for l in L:P[l] = areturn adef unite(a, b):if par(a) != par(b):if P[par(b)] >= P[par(a)]:if P[par(b)] == P[par(a)]: P[par(a)] -= 1NE[LA[par(a)]] = par(b)LA[par(a)] = LA[par(b)]P[par(b)] = par(a)else:NE[LA[par(b)]] = par(a)LA[par(b)] = LA[par(a)]P[par(a)] = par(b)X = []for _ in range(Q):t, a, b = map(int, input().split())X.append((t, a, b))for t, a, b in X:if t == 1:a, b = a-1, b-1unite(a, b)DONE = [0] * NID = [-1] * NIDI = [-1] * Nc = 0for i in range(N):if DONE[i]: continuea = par(i)ID[a] = cIDI[c] = aDONE[a] = 1c += 1while NE[a] >= 0:a = NE[a]ID[a] = cIDI[c] = aDONE[a] = 1c += 1NN = 19BIT=[0]*(2**NN+1)def addrange(l0, r0, x=1):l, r = l0, r0while l <= 2**NN:BIT[l] += xl += l & (-l)while r <= 2**NN:BIT[r] -= xr += r & (-r)def getvalue(r):a = 0while r != 0:a += BIT[r]r -= r&(-r)return aP = [-1 for i in range(N)]LA = [i for i in range(N)]NE = [-1] * NANS = []for t, a, b in X:if t == 1:a, b = a-1, b-1unite(a, b)elif t == 2:a -= 1a = par(a)addrange(ID[a] + 1, ID[LA[a]] + 2, b)else:a -= 1ANS.append(getvalue(ID[a] + 1))print("\n".join(map(str, ANS)))