結果
問題 | No.1917 LCMST |
ユーザー | siganai |
提出日時 | 2022-05-01 20:30:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,726 ms / 4,000 ms |
コード長 | 2,360 bytes |
コンパイル時間 | 863 ms |
コンパイル使用メモリ | 86,756 KB |
実行使用メモリ | 380,628 KB |
最終ジャッジ日時 | 2023-09-13 13:19:07 |
合計ジャッジ時間 | 63,861 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 154 ms
81,444 KB |
testcase_01 | AC | 158 ms
81,168 KB |
testcase_02 | AC | 154 ms
81,244 KB |
testcase_03 | AC | 210 ms
87,764 KB |
testcase_04 | AC | 197 ms
88,088 KB |
testcase_05 | AC | 206 ms
87,908 KB |
testcase_06 | AC | 204 ms
88,068 KB |
testcase_07 | AC | 201 ms
88,276 KB |
testcase_08 | AC | 157 ms
81,432 KB |
testcase_09 | AC | 2,435 ms
376,872 KB |
testcase_10 | AC | 2,678 ms
379,348 KB |
testcase_11 | AC | 2,281 ms
376,848 KB |
testcase_12 | AC | 1,778 ms
337,440 KB |
testcase_13 | AC | 786 ms
249,528 KB |
testcase_14 | AC | 2,242 ms
358,216 KB |
testcase_15 | AC | 604 ms
247,812 KB |
testcase_16 | AC | 834 ms
251,684 KB |
testcase_17 | AC | 1,170 ms
295,468 KB |
testcase_18 | AC | 1,363 ms
315,464 KB |
testcase_19 | AC | 649 ms
247,712 KB |
testcase_20 | AC | 546 ms
247,896 KB |
testcase_21 | AC | 655 ms
247,600 KB |
testcase_22 | AC | 545 ms
247,720 KB |
testcase_23 | AC | 533 ms
247,804 KB |
testcase_24 | AC | 645 ms
248,076 KB |
testcase_25 | AC | 542 ms
247,596 KB |
testcase_26 | AC | 589 ms
247,784 KB |
testcase_27 | AC | 602 ms
247,692 KB |
testcase_28 | AC | 629 ms
247,804 KB |
testcase_29 | AC | 2,617 ms
380,576 KB |
testcase_30 | AC | 2,656 ms
380,568 KB |
testcase_31 | AC | 2,693 ms
380,176 KB |
testcase_32 | AC | 2,726 ms
380,232 KB |
testcase_33 | AC | 2,711 ms
380,628 KB |
testcase_34 | AC | 374 ms
245,684 KB |
testcase_35 | AC | 364 ms
245,868 KB |
testcase_36 | AC | 358 ms
246,356 KB |
testcase_37 | AC | 2,624 ms
379,996 KB |
testcase_38 | AC | 2,630 ms
380,228 KB |
testcase_39 | AC | 2,596 ms
380,444 KB |
testcase_40 | AC | 2,627 ms
380,612 KB |
testcase_41 | AC | 2,647 ms
380,272 KB |
testcase_42 | AC | 2,587 ms
380,148 KB |
testcase_43 | AC | 396 ms
246,452 KB |
testcase_44 | AC | 398 ms
247,204 KB |
ソースコード
#!/usr/bin/env PyPy3 from collections import Counter, defaultdict, deque import itertools import re import math from functools import reduce import operator import bisect from heapq import * import functools mod=998244353 import sys input=sys.stdin.readline class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): now = x tmpl = [] while self.parents[now] >= 0: tmpl.append(now) now = self.parents[now] for xx in tmpl: self.parents[xx] = now return now def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return x if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x return x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) def members(self, x):#O(n)かかる。全部求めたい場合は、all_group_membersを使う。 root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items()) maxa = 10 ** 5 + 1 n = int(input()) a = list(map(int,input().split())) l = [-1] * maxa uf = UnionFind(n) ans = 0 for i,aa in enumerate(a): if l[aa] == -1: l[aa] = i else: ans += aa ca = [[] for _ in range(maxa)] for i in range(1,maxa): for j in range(1,maxa): if i * j > maxa - 1: break if l[i * j] != -1: ca[i].append([i * j,l[i * j]]) edge = [] for i in range(1,maxa): for j in range(1,len(ca[i])): edge.append([ca[i][0][0] * ca[i][j][0] // i,ca[i][0][1],ca[i][j][1]]) edge.sort(key = operator.itemgetter(0)) for dis,i,j in edge: if uf.same(i,j): continue ans += dis uf.union(i,j) print(ans)