結果
問題 |
No.1054 Union add query
|
ユーザー |
👑 ![]() |
提出日時 | 2025-07-17 00:05:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,827 ms / 2,000 ms |
コード長 | 2,606 bytes |
コンパイル時間 | 430 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 223,220 KB |
最終ジャッジ日時 | 2025-07-17 00:05:40 |
合計ジャッジ時間 | 12,177 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
""" https://yukicoder.me/problems/no/1054 mergeするときに、親頂点を追加 各頂点に、(今判明している最高の頂点、その頂点を除くパス上の重み和) を管理 """ import sys from sys import stdin class DSU(): def __init__(self, n:int): self.n = n self.p = [i for i in range(n)] self.rank = [i for i in range(n)] self.sizelis = [1] * n def leader(self,a): stk = [] while self.p[a] != a: stk.append(a) a = self.p[a] for v in stk: self.p[v] = a return a def merge(self, a, b): ap = self.leader(a) bp = self.leader(b) if ap == bp: return ap if self.rank[ap] > self.rank[bp]: self.p[bp] = ap self.sizelis[ap] += self.sizelis[bp] elif self.rank[ap] < self.rank[bp]: self.p[ap] = bp self.sizelis[bp] += self.sizelis[ap] else: self.p[bp] = ap self.sizelis[ap] += self.sizelis[bp] self.rank[ap] += 1 return self.p[ap] def same(self,a,b): return self.leader(a) == self.leader(b) def size(self,a): return self.sizelis[ self.leader(a) ] def groups(self): dic = {} for v in range(self.n): vp = self.leader(v) if vp not in dic: dic[vp] = [v] else: dic[vp].append(v) return list(dic.values()) N,Q = map(int,stdin.readline().split()) uf = DSU(N) lis = [ [None,0] for i in range(N) ] # 頂点vから、親と、そこまでのコストを求める def search(v): vs = [ v ] while lis[v][0] != None: v = lis[v][0] vs.append(v) # 縮約する costs = [] cost = 0 for i,v in enumerate(list(reversed(vs))): if i != 0: cost += lis[v][1] costs.append(cost) costs.reverse() for v,c in zip(vs[:-1],costs[:-1]): lis[v] = [ vs[-1] , c ] return vs[-1] , cost + lis[vs[-1]][1] ANS = [] for qidx in range(Q): T,A,B = map(int,stdin.readline().split()) if T == 1: A -= 1 B -= 1 if not uf.same(A,B): uf.merge(A,B) pa,_ = search(A) pb,_ = search(B) vidx = len(lis) lis[pa][0] = vidx lis[pb][0] = vidx lis.append( [None,0] ) elif T == 2: A -= 1 pa,_ = search(A) lis[pa][1] += B else: A -= 1 ANS.append(search(A)[1]) print (*ANS,sep="\n")