結果
| 問題 |
No.1917 LCMST
|
| コンテスト | |
| ユーザー |
 とりゐ
|
| 提出日時 | 2022-03-01 06:53:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,434 bytes |
| コンパイル時間 | 318 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 851,328 KB |
| 最終ジャッジ日時 | 2024-06-28 08:02:24 |
| 合計ジャッジ時間 | 9,500 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 6 MLE * 1 -- * 35 |
ソースコード
import math
class FibonacciHeap:
# internal node class
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.parent = self.child = self.left = self.right = None
self.degree = 0
self.mark = False
# function to iterate through a doubly linked list
def iterate(self, head):
node = stop = head
flag = False
while True:
if node == stop and flag is True:
break
elif node == stop:
flag = True
yield node
node = node.right
# pointer to the head and minimum node in the root list
root_list, min_node = None, None
# maintain total node count in full fibonacci heap
total_nodes = 0
# return min node in O(1) time
def find_min(self):
return self.min_node
# extract (delete) the min node from the heap in O(log n) time
# amortized cost analysis can be found here (http://bit.ly/1ow1Clm)
def extract_min(self):
z = self.min_node
if z is not None:
if z.child is not None:
# attach child nodes to root list
children = [x for x in self.iterate(z.child)]
for i in range(0, len(children)):
self.merge_with_root_list(children[i])
children[i].parent = None
self.remove_from_root_list(z)
# set new min node in heap
if z == z.right:
self.min_node = self.root_list = None
else:
self.min_node = z.right
self.consolidate()
self.total_nodes -= 1
return z
# insert new node into the unordered root list in O(1) time
# returns the node so that it can be used for decrease_key later
def insert(self, key, value=None):
n = self.Node(key, value)
n.left = n.right = n
self.merge_with_root_list(n)
if self.min_node is None or n.key < self.min_node.key:
self.min_node = n
self.total_nodes += 1
return n
# modify the key of some node in the heap in O(1) time
def decrease_key(self, x, k):
if k > x.key:
return None
x.key = k
y = x.parent
if y is not None and x.key < y.key:
self.cut(x, y)
self.cascading_cut(y)
if x.key < self.min_node.key:
self.min_node = x
# merge two fibonacci heaps in O(1) time by concatenating the root lists
# the root of the new root list becomes equal to the first list and the second
# list is simply appended to the end (then the proper min node is determined)
def merge(self, h2):
H = FibonacciHeap()
H.root_list, H.min_node = self.root_list, self.min_node
# fix pointers when merging the two heaps
last = h2.root_list.left
h2.root_list.left = H.root_list.left
H.root_list.left.right = h2.root_list
H.root_list.left = last
H.root_list.left.right = H.root_list
# update min node if needed
if h2.min_node.key < H.min_node.key:
H.min_node = h2.min_node
# update total nodes
H.total_nodes = self.total_nodes + h2.total_nodes
return H
# if a child node becomes smaller than its parent node we
# cut this child node off and bring it up to the root list
def cut(self, x, y):
self.remove_from_child_list(y, x)
y.degree -= 1
self.merge_with_root_list(x)
x.parent = None
x.mark = False
# cascading cut of parent node to obtain good time bounds
def cascading_cut(self, y):
z = y.parent
if z is not None:
if y.mark is False:
y.mark = True
else:
self.cut(y, z)
self.cascading_cut(z)
# combine root nodes of equal degree to consolidate the heap
# by creating a list of unordered binomial trees
def consolidate(self):
A = [None] * int(math.log(self.total_nodes) * 2)
nodes = [w for w in self.iterate(self.root_list)]
for w in range(0, len(nodes)):
x = nodes[w]
d = x.degree
while A[d] != None:
y = A[d]
if x.key > y.key:
temp = x
x, y = y, temp
self.heap_link(y, x)
A[d] = None
d += 1
A[d] = x
# find new min node - no need to reconstruct new root list below
# because root list was iteratively changing as we were moving
# nodes around in the above loop
for i in range(0, len(A)):
if A[i] is not None:
if A[i].key < self.min_node.key:
self.min_node = A[i]
# actual linking of one node to another in the root list
# while also updating the child linked list
def heap_link(self, y, x):
self.remove_from_root_list(y)
y.left = y.right = y
self.merge_with_child_list(x, y)
x.degree += 1
y.parent = x
y.mark = False
# merge a node with the doubly linked root list
def merge_with_root_list(self, node):
if self.root_list is None:
self.root_list = node
else:
node.right = self.root_list.right
node.left = self.root_list
self.root_list.right.left = node
self.root_list.right = node
# merge a node with the doubly linked child list of a root node
def merge_with_child_list(self, parent, node):
if parent.child is None:
parent.child = node
else:
node.right = parent.child.right
node.left = parent.child
parent.child.right.left = node
parent.child.right = node
# remove a node from the doubly linked root list
def remove_from_root_list(self, node):
if node == self.root_list:
self.root_list = node.right
node.left.right = node.right
node.right.left = node.left
# remove a node from the doubly linked child list
def remove_from_child_list(self, parent, node):
if parent.child == parent.child.right:
parent.child = None
elif parent.child == node:
parent.child = node.right
node.right.parent = parent
node.left.right = node.right
node.right.left = node.left
from heapq import heappush, heappop, heapify
def MST(n,edge):
used=[0]*n
f=FibonacciHeap()
for c,v in edge[0]:
f.insert((c,v))
used[0]=1
ans=0
tmp=1
while tmp<n:
m=f.extract_min()
cost,v=m.key
if used[v]:
continue
used[v]=1
tmp+=1
ans+=cost
for c,w in edge[v]:
if used[w]:
continue
f.insert((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)