Submission #1085924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085924		Peptic	Bosses (BOI16_bosses)	Cpython 3	0 / 100	11 ms	3168 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)
    if val in boss:
        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(value)
print(sum(value.values()))

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