oj.uz

Submission #88554

# Submission time Handle Problem Language Result Execution time Memory
88554 2018-12-06T12:16:47 Z Gogotchuri Triumphal arch (POI13_luk) Python 3
60 / 100
 2000 ms 69572 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3300 KB Output is correct
2 Correct 26 ms 3348 KB Output is correct
3 Correct 24 ms 3500 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3528 KB Output is correct
2 Correct 27 ms 3568 KB Output is correct
3 Correct 26 ms 3612 KB Output is correct
4 Correct 25 ms 3612 KB Output is correct
5 Correct 25 ms 3612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3612 KB Output is correct
2 Correct 27 ms 3612 KB Output is correct
3 Correct 25 ms 3612 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3712 KB Output is correct
2 Correct 38 ms 3776 KB Output is correct
3 Correct 39 ms 3776 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 5412 KB Output is correct
2 Correct 232 ms 9228 KB Output is correct
3 Correct 187 ms 9228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 9612 KB Output is correct
2 Correct 997 ms 24892 KB Output is correct
3 Correct 561 ms 24892 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 24892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2023 ms 44092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 65708 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 69572 KB Time limit exceeded
2 Halted 0 ms 0 KB -