結果

問題 No.1917 LCMST
ユーザー とりゐ
提出日時 2022-02-28 14:05:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,992 ms / 4,000 ms
コード長 868 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 273,136 KB
最終ジャッジ日時 2024-06-28 08:02:14
合計ジャッジ時間 61,115 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop, heapify
def MST(n,edge):
  used=[0]*n
  todo=edge[0].copy()
  used[0]=1
  heapify(todo)
  ans=0
  while todo:
    cost,v=heappop(todo)
    if used[v]:
      continue
    used[v] = 1
    ans+=cost
    for c,w in edge[v]:
      if used[w]:
          continue
      heappush(todo,(c,w))
  return ans

n=int(input())
a=list(map(int,input().split()))
m=10**5
d=[-1]*(m+1)
cnt=[0]*(m+1)

ans=0
for i in a:
  if cnt[i]==0:
    cnt[i]=1
  else:
    ans+=i


id=[-1]*(m+1)
size=0
for i in range(m+1):
  if cnt[i]:
    id[i]=size
    size+=1
edge=[[] for i in range(size)]
for i in range(1,m+1):
  for j in range(i,m+1,i):
    if cnt[j]==1:
      if d[i]==-1:
        d[i]=j
      else:
        id1=id[j]
        id2=id[d[i]]
        edge[id1].append((d[i]*j//i,id2))
        edge[id2].append((d[i]*j//i,id1))

ans+=MST(size,edge)
print(ans)
0