結果
問題 |
No.1917 LCMST
|
ユーザー |
👑 ![]() |
提出日時 | 2025-10-04 19:28:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,587 ms / 4,000 ms |
コード長 | 2,175 bytes |
コンパイル時間 | 773 ms |
コンパイル使用メモリ | 82,916 KB |
実行使用メモリ | 288,800 KB |
最終ジャッジ日時 | 2025-10-04 19:29:54 |
合計ジャッジ時間 | 54,160 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
""" https://yukicoder.me/problems/no/1917 A*B // gcd(A,B) gcdが大きいほうがいいのはそうなので gcdが大きいほうから探索していく? 1 7 13 で7,13をくっつけるのは損でしかない... --- 辺を削れるらしい gcdを決め撃つと、最小の奴にくっつけていくウニグラフが正義 これでlogになるか """ 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 = int(input()) A = list(map(int,input().split())) ans = 0 D = [0] * 100001 for v in A: if D[v] == 0: D[v] = 1 else: ans += v e = [] for g in range(1,100001): nmin = None for v in range(g,100001,g): if D[v]: if nmin == None: nmin = v else: e.append( ( v*nmin // g , v , nmin ) ) e.sort() # print (ans) uf = DSU(100001) for cost,l,r in e: if not uf.same(l,r): ans += cost uf.merge(l,r) print (ans)