結果
問題 |
No.3087 University Coloring
|
ユーザー |
![]() |
提出日時 | 2025-04-04 22:41:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 921 ms / 2,000 ms |
コード長 | 1,613 bytes |
コンパイル時間 | 574 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 110,564 KB |
最終ジャッジ日時 | 2025-04-04 22:43:13 |
合計ジャッジ時間 | 24,232 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
""" """ 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,M = map(int,stdin.readline().split()) uf = DSU(N) cab = [] for i in range(M): a,b,c = map(int,stdin.readline().split()) cab.append( (c,a-1,b-1) ) cab.sort() cab.reverse() ans = 0 for c,a,b in cab: if not uf.same(a,b): uf.merge(a,b) ans += c*2 print (ans)