## Submission #88585

# Submission time Handle Problem Language Result Execution time Memory
88585 2018-12-06T21:41:31 Z Gogotchuri Triumphal arch (POI13_luk) Python 3
60 / 100
2000 ms 68364 KB
```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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3428 KB Output is correct
2 Correct 24 ms 3440 KB Output is correct
3 Correct 24 ms 3492 KB Output is correct

#### Subtask #2 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3492 KB Output is correct
2 Correct 25 ms 3492 KB Output is correct
3 Correct 24 ms 3492 KB Output is correct
4 Correct 24 ms 3492 KB Output is correct
5 Correct 25 ms 3704 KB Output is correct

#### Subtask #3 10.0 / 10.0

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

#### Subtask #4 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3728 KB Output is correct
2 Correct 35 ms 4000 KB Output is correct
3 Correct 34 ms 4000 KB Output is correct

#### Subtask #5 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 5704 KB Output is correct
2 Correct 217 ms 9748 KB Output is correct
3 Correct 157 ms 9748 KB Output is correct

#### Subtask #6 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 10624 KB Output is correct
2 Correct 962 ms 26432 KB Output is correct
3 Correct 504 ms 26432 KB Output is correct

#### Subtask #7 0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 26432 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 2064 ms 47224 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 2068 ms 68364 KB Time limit exceeded

#### Subtask #10 0 / 10.0

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