Submission #88585

#	Time	Username	Problem	Language	Result	Execution time	Memory
88585		Gogotchuri	Triumphal arch (POI13_luk)	Cpython 3	60 / 100	2068 ms	68364 KiB

luk

import sys
sys.setrecursionlimit(200000)

def depth_first(h, p, t, ls, memo):

    memo[h] = t - len(ls[h])
    memo[h] += 0 if p == 0 else 1

    for elem in ls[h]:
        if elem == p:
            continue

        depth_first(elem, h, t, ls, memo)

        if memo[elem] < 0:
        	memo[h] += memo[elem]


def main():
    n = int(input())
    ls = [[] for i in range(n + 2)]
    memo = [0 for i in range(n + 2)]
    for _ in range(n - 1):
        f, s = map(int, input().split())
        ls[f].append(s)
        ls[s].append(f)    
    s = 0
    e = n
    while s < e:
        m = (s + e)//2
        t = m
        depth_first(1, 0, t, ls, memo)
        if memo[1] < 0:
        	s = m + 1 
        else:
        	e = m

    print(s)

if __name__ == "__main__":
    main()

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10