結果
問題 | No.1917 LCMST |
ユーザー | とりゐ |
提出日時 | 2022-02-28 14:05:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,556 ms / 4,000 ms |
コード長 | 868 bytes |
コンパイル時間 | 483 ms |
コンパイル使用メモリ | 86,996 KB |
実行使用メモリ | 275,796 KB |
最終ジャッジ日時 | 2023-09-10 16:56:57 |
合計ジャッジ時間 | 54,043 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 88 ms
78,680 KB |
testcase_01 | AC | 91 ms
78,708 KB |
testcase_02 | AC | 89 ms
78,904 KB |
testcase_03 | AC | 155 ms
81,144 KB |
testcase_04 | AC | 144 ms
81,428 KB |
testcase_05 | AC | 154 ms
80,900 KB |
testcase_06 | AC | 162 ms
81,304 KB |
testcase_07 | AC | 144 ms
81,056 KB |
testcase_08 | AC | 89 ms
78,728 KB |
testcase_09 | AC | 2,170 ms
270,456 KB |
testcase_10 | AC | 2,161 ms
270,832 KB |
testcase_11 | AC | 2,178 ms
272,080 KB |
testcase_12 | AC | 1,840 ms
263,996 KB |
testcase_13 | AC | 793 ms
246,136 KB |
testcase_14 | AC | 1,947 ms
269,312 KB |
testcase_15 | AC | 580 ms
245,440 KB |
testcase_16 | AC | 857 ms
245,832 KB |
testcase_17 | AC | 1,162 ms
246,888 KB |
testcase_18 | AC | 1,325 ms
246,692 KB |
testcase_19 | AC | 572 ms
245,208 KB |
testcase_20 | AC | 477 ms
244,564 KB |
testcase_21 | AC | 593 ms
245,392 KB |
testcase_22 | AC | 480 ms
245,104 KB |
testcase_23 | AC | 468 ms
244,908 KB |
testcase_24 | AC | 581 ms
245,404 KB |
testcase_25 | AC | 513 ms
245,032 KB |
testcase_26 | AC | 524 ms
245,092 KB |
testcase_27 | AC | 533 ms
245,016 KB |
testcase_28 | AC | 562 ms
245,012 KB |
testcase_29 | AC | 2,295 ms
275,796 KB |
testcase_30 | AC | 2,261 ms
275,544 KB |
testcase_31 | AC | 2,371 ms
275,488 KB |
testcase_32 | AC | 2,320 ms
275,552 KB |
testcase_33 | AC | 2,300 ms
275,764 KB |
testcase_34 | AC | 274 ms
245,336 KB |
testcase_35 | AC | 275 ms
245,400 KB |
testcase_36 | AC | 275 ms
245,412 KB |
testcase_37 | AC | 2,556 ms
274,052 KB |
testcase_38 | AC | 2,418 ms
274,100 KB |
testcase_39 | AC | 2,476 ms
273,832 KB |
testcase_40 | AC | 2,516 ms
274,712 KB |
testcase_41 | AC | 2,462 ms
273,976 KB |
testcase_42 | AC | 2,427 ms
274,132 KB |
testcase_43 | AC | 330 ms
244,112 KB |
testcase_44 | AC | 337 ms
245,300 KB |
ソースコード
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)