結果
問題 | No.1054 Union add query |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2020-05-15 22:24:05 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,288 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 81,832 KB |
実行使用メモリ | 175,652 KB |
最終ジャッジ日時 | 2023-10-19 15:03:52 |
合計ジャッジ時間 | 14,393 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
53,424 KB |
testcase_01 | AC | 41 ms
53,424 KB |
testcase_02 | AC | 40 ms
53,424 KB |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | AC | 1,209 ms
114,728 KB |
testcase_07 | AC | 986 ms
113,452 KB |
testcase_08 | AC | 1,067 ms
120,120 KB |
testcase_09 | AC | 1,411 ms
147,168 KB |
testcase_10 | AC | 669 ms
175,652 KB |
ソースコード
import bisect def uf_find(n,p,slis): allsum = 0 time = -1 while p[n] != n: ind = bisect.bisect_left(slis[n],(time,0)) - 1 allsum += slis[n][-1][1] - slis[n][ind][1] time = max(time , linktime[n]) n = p[n] ind = bisect.bisect_left(slis[n],(time,0)) - 1 allsum += slis[n][-1][1] - slis[n][ind][1] return n,allsum def uf_union(a,b,p,rank,slis): ap,tmp = uf_find(a,p,slis) bp,tmp = uf_find(b,p,slis) if ap == bp: return True else: if rank[ap] > rank[bp]: p[bp] = ap linktime[bp] = loop elif rank[ap] < rank[bp]: p[ap] = bp linktime[ap] = loop else: p[bp] = ap rank[ap] += 1 linktime[bp] = loop return False N,Q = map(int,input().split()) TAB = [] p = [i for i in range(N)] rank = [1] * N slis = [[(-2,0)] for i in range(N)] linktime = [-1] * N for loop in range(Q): t,a,b = map(int,input().split()) a -= 1 if t == 1: b -= 1 uf_union(a,b,p,rank,slis) elif t == 2: nowp,asum = uf_find(a,p,slis) slis[nowp].append((loop,slis[nowp][-1][1] + b)) else: nowp,asum = uf_find(a,p,slis) print (asum)