제출 #1084753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084753		Izzy	Bosses (BOI16_bosses)	Cpython 3	67 / 100	1557 ms	3932 KiB

bosses

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33