Submission #1085302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085302		Peptic	Bosses (BOI16_bosses)	Cpython 3	0 / 100	11 ms	2908 KiB

bosses

def calculate(x, y):
    s = 0
    for thing in tree[x+1][y]:
        s+= value[thing]
    return s


n = int(input())
boss= {}
for i in range(n):
    cur = list(map(int, input().split()))
    for d in range(cur[0]):
        if cur[d+1] not in boss:
            boss[cur[d+1]] = []
        boss[cur[d+1]].append(i+1)

order = [k for k,v in sorted(boss.items(), key=lambda item: -len(item[1]))]
seen = set([order[0]])
q = [order[0]]
tree = [[order[0]]]

while len(seen) != n:
    tree.append([])
    for i in range(len(q)):
        cur= q.pop(0)
        c = []
        for thing in boss[cur]:
            if thing not in seen:
                seen.add(thing)
                c.append(thing)
                q.append(thing)
        tree[-1].append(c)

value = {i+1:1 for i in range(n)}
# print(value)
# print(tree)
for i in reversed(range(n-2)):
    for d in range(len(tree[i])):
        # print(tree[i][d])
        if type(tree[i][d]) == list:
            for c in range(len(tree[i][d])):
                # print(tree[i][d][c], i , d, c)
                value[tree[i][d][c]]+= calculate(i, c)
        else:
            # print(tree[i][d], i, d)
            value[tree[i][d]]+= calculate(i,d)
    # print("break")
        # value[tree[-i-2][d]]+=calculate(n-i-2, d)
print(sum(value.values()))

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33