제출 #1085306

#제출 시각아이디문제언어결과실행 시간메모리
1085306PepticBosses (BOI16_bosses)Cpython 3
0 / 100
11 ms3104 KiB
def calculate(x, y):
    s = 0
    # print(x, y)
    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]]]
value = {i+1:1 for i in range(n)}


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

for i in reversed(range(len(tree)-1)):
    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()))

























# 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)





# # print(value)
# # print(tree)
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...