Submission #88885

#	Time	Username	Problem	Language	Result	Execution time	Memory
88885		sailormoon	Triumphal arch (POI13_luk)	Cpython 3	30 / 100	2065 ms	66264 KiB

luk

graph = dict()
visited = list()
visited = [False for i in range(300001)]
######################
n = int(input())
######################

def canHandle(v, crs):
    num_children = 0
    need_crews = 0
    visited[v] = True
    for i in range(len(graph[v])):
        if visited[graph[v][i]] == False:
            num_children += 1
            need_crews += canHandle(graph[v][i], crs)
    return max(0, num_children + need_crews - crs)

start = 0
end = n
for i in range(0, n - 1):
    x = input()
    x = x.split()
    a = int(x[0])
    b = int(x[1])
    for_a = list()
    for_b = list()
    if a in graph and b in graph:
        graph[a].append(b)
        graph[b].append(a)
    elif a in graph:
        graph[a].append(b)
        for_b = list()
        for_b.append(a)
        graph[b] = for_b
    elif b in graph:
        graph[b].append(a)  
        for_a = list()
        for_a.append(b)
        graph[a] = for_a
    else:
        for_a = list()
        for_b = list()
        for_a.append(b)
        for_b.append(a)
        graph[a] = for_a
        graph[b] = for_b

while start < end:
    midpoint = int((start + end) / 2)
    for i in range(n):
        visited[i] = False
    if canHandle(1, midpoint) == 0: 
        end = midpoint
    else:
        start = 1 + midpoint
print(start)

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