Submission #88554

#	Time	Username	Problem	Language	Result	Execution time	Memory
88554		Gogotchuri	Triumphal arch (POI13_luk)	Cpython 3	60 / 100	2073 ms	69572 KiB

luk

import sys
sys.setrecursionlimit(200000)

def depth_first(h, p, t, ls, memo):
    sm = 0
    for elem in ls[h]:
        if elem == p:
            continue
        depth_first(elem, h, t, ls, memo)
        sm += memo[elem]
    memo[h] = max(sm - t + 1, 1)


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())
        f -= 1
        s -= 1
        ls[f].append(s)
        ls[s].append(f)    
    s = 0
    e = n
    while not s > e:
        m = (s + e) >> 1
        t = m
        depth_first(0, -1, t, ls, memo)
        if memo[0] > 1:
            s = m + 1
        else:
            e = m-1

    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