oj.uz

Submission #883195

# Submission time Handle Problem Language Result Execution time Memory
883195 2023-12-04T18:25:49 Z SansPapyrus683 Sirni (COCI17_sirni) PyPy 3
0 / 140
 850 ms 490452 KB 
# 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 733 ms 488676 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 21240 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 720 ms 488224 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 272 ms 68260 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 67420 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 271 ms 68132 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 32356 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 850 ms 490388 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 841 ms 490452 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 762 ms 488836 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -