oj.uz

Submission #1084138

# Submission time Handle Problem Language Result Execution time Memory
1084138 2024-09-05T10:31:45 Z stefdasca Bosses (BOI16_bosses) PyPy 3
67 / 100
 1500 ms 29688 KB 
def test(start):
    visited = [False for i in range(n)]
    levels = [[start]]
    lvl = 0
    pos = 0
    salary = 0
    visited[start] = True
    while lvl < len(levels):
        # print(levels, salary)
        start = levels[lvl][pos]
        if start in arr:
            for i in arr[start]:
                if not visited[i]:
                    visited[i] = True
                    if len(levels) > lvl + 1:
                        levels[lvl + 1].append(i)
                    else:
                        levels.append([i])
        pos += 1
        if pos == len(levels[lvl]):
            salary += len(levels[lvl]) * (lvl + 1)
            lvl += 1
            pos = 0
    a = set(visited)
    if True in a and len(a) == 1:
        # print(levels)
        return salary
    return float('inf')


salary = float('inf')
n = int(input())
arr = {}
for i in range(n):
    x = [int(i) - 1 for i in input().split(' ')[1:]]
    for j in x:
        if j in arr:
            arr[j].append(i)
        else:
            arr[j] = [i]

for i in arr:
    salary = min(salary, test(i))
print(salary)

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18228 KB Output is correct
2 Correct 28 ms 18236 KB Output is correct
3 Correct 27 ms 18220 KB Output is correct
4 Correct 29 ms 18200 KB Output is correct
5 Correct 34 ms 18224 KB Output is correct
6 Correct 29 ms 18392 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18228 KB Output is correct
2 Correct 28 ms 18236 KB Output is correct
3 Correct 27 ms 18220 KB Output is correct
4 Correct 29 ms 18200 KB Output is correct
5 Correct 34 ms 18224 KB Output is correct
6 Correct 29 ms 18392 KB Output is correct
7 Correct 35 ms 19040 KB Output is correct
8 Correct 40 ms 19744 KB Output is correct
9 Correct 36 ms 19228 KB Output is correct
10 Correct 45 ms 19764 KB Output is correct
11 Correct 44 ms 19756 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18228 KB Output is correct
2 Correct 28 ms 18236 KB Output is correct
3 Correct 27 ms 18220 KB Output is correct
4 Correct 29 ms 18200 KB Output is correct
5 Correct 34 ms 18224 KB Output is correct
6 Correct 29 ms 18392 KB Output is correct
7 Correct 35 ms 19040 KB Output is correct
8 Correct 40 ms 19744 KB Output is correct
9 Correct 36 ms 19228 KB Output is correct
10 Correct 45 ms 19764 KB Output is correct
11 Correct 44 ms 19756 KB Output is correct
12 Correct 52 ms 20504 KB Output is correct
13 Correct 48 ms 20268 KB Output is correct
14 Correct 954 ms 29688 KB Output is correct
15 Correct 291 ms 26932 KB Output is correct
16 Execution timed out 1588 ms 28724 KB Time limit exceeded
17 Halted 0 ms 0 KB -