oj.uz

답안 #88885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88885 2018-12-09T18:07:09 Z sailormoon Triumphal arch (POI13_luk) Python 3
30 / 100
 2000 ms 66264 KB 
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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 5784 KB Output is correct
2 Correct 43 ms 5784 KB Output is correct
3 Correct 44 ms 5836 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 6032 KB Output is correct
2 Correct 47 ms 6032 KB Output is correct
3 Correct 42 ms 6032 KB Output is correct
4 Incorrect 41 ms 6032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 6032 KB Output is correct
2 Correct 49 ms 6100 KB Output is correct
3 Correct 43 ms 6100 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 6108 KB Output is correct
2 Correct 74 ms 6372 KB Output is correct
3 Correct 65 ms 6372 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 8076 KB Output is correct
2 Runtime error 105 ms 9024 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1192 ms 12684 KB Output is correct
2 Runtime error 216 ms 13876 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2063 ms 28624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 50000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 66264 KB Time limit exceeded

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 66264 KB Time limit exceeded
2 Halted 0 ms 0 KB -