Submission #1085923

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

bosses

class Node:
     
    def __init__(self, key):
         
        self.key = key
        self.child = []
   
 # Utility function to create a new tree node
def newNode(key):    
    temp = Node(key)
    return temp
     
# Prints the n-ary tree level wise
def LevelOrderTraversal(root):
 
    if (root == None):
        return;
   
    # Standard level order traversal code
    # using queue
    q = []  # Create a queue
    q.append(root); # Enqueue root 
    while (len(q) != 0):
     
        n = len(q);
  
        # If this node has children
        while (n > 0):
         
            # Dequeue an item from queue and print it
            p = q[0]
            q.pop(0);
            print(p.key, end=' ')
   
            # Enqueue all children of the dequeued item
            for i in range(len(p.child)):
             
                q.append(p.child[i]);
            n -= 1
   
        print() # Print new line between two levels

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]])
value = {i+1:1 for i in range(n)}
root = newNode(order[0])


def create(val, node):
    seen.add(val)
    for thing in boss[val]:
        # seen.add(thing)
        if thing not in seen:
            seen.add(thing)
            holder = newNode(thing)
            holder.key = thing
            (node.child).append((holder))

    for i in range(min(len(node.child), len(boss[val]))):
        thing = boss[val][i]
        create(thing, node.child[i])
create(order[0], root)
# LevelOrderTraversal(root)

def calculate(node):
    for i in range(len(node.child)):
        if len(node.child[i].child) != 0:
            calculate(node.child[i])
        value[node.key]+= value[node.child[i].key]

# print("break")

# print(calculate(root))
calculate(root)
print(sum(value.values()))












# 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 thing in tree:
#     print(thing)
# for i in reversed(range(len(tree)-1)):
#     for d in range(len(tree[i])):
#         if type(tree[i][d]) == list:
#             for c in range(len(tree[i][d])):
#                 value[tree[i][d][c]]+= calculate(i, c)
#         else:
#             value[tree[i][d]]+= calculate(i,d)
# print(sum(value.values()))

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