Submission #883196

#	Time	Username	Problem	Language	Result	Execution time	Memory
883196		SansPapyrus683	Sirni (COCI17_sirni)	Pypy 3	84 / 140	2005 ms	786432 KiB

sirni

# BeginCodeSnip{DSU (from the module)}
class DisjointSets:
    def __init__(self, size: int) -> None:
        self.parents = [-1 for _ in range(size)]
        self.sizes = [1 for _ in range(size)]

    # finds the "representative" node in a's component
    def find(self, x: int) -> int:
        if self.parents[x] == -1:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    # returns whether the merge changed connectivity
    def unite(self, x: int, y: int) -> bool:
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False

        if self.sizes[x_root] < self.sizes[y_root]:
            x_root, y_root = y_root, x_root
        self.parents[y_root] = x_root
        self.sizes[x_root] += self.sizes[y_root]
        return True

    # returns whether two nodes are in the same connected component
    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
# EndCodeSnip


cards = sorted({int(input()) for _ in range(int(input()))})

largest = cards[-1]  # since we sorted the cards already
# next_largest[i] contains the index of lowest card value that's >= i
next_largest = [-1 for _ in range(largest + 1)]
for i, c in enumerate(cards):
    next_largest[c] = i
for c in range(largest - 1, -1, -1):
    # if this isn't assigned yet, assign it the previous one
    if next_largest[c] == -1:
        next_largest[c] = next_largest[c + 1]

good_links = [[] for _ in range(largest + 1)]
for i in range(len(cards) - 1):
    good_links[cards[i + 1] % cards[i]].append((i, i + 1))
    at = 2 * cards[i]
    while at <= largest:
        good_mod = next_largest[at]
        good_links[cards[good_mod] % cards[i]].append((i, good_mod))
        at += cards[i]

total_cost = 0
linked_cards = DisjointSets(len(cards))
for c in range(largest + 1):
    for a, b in good_links[c]:
        result = linked_cards.unite(a, b)
        total_cost += c * result

print(total_cost)

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14