oj.uz

Submission #124797

# Submission time Handle Problem Language Result Execution time Memory
124797 2019-07-04T02:08:33 Z model_code Cat in a tree (BOI17_catinatree) Python 3
100 / 100
 822 ms 35188 KB 
#!/usr/bin/env python3
import sys, math
INF = 100000000

def catinatree():
    # Read input
    n, d = map(int, sys.stdin.readline().split())
    children = [[] for i in range(n)]
    for i in range(1, n):
        children[int(sys.stdin.readline().strip())].append(i)
    
    # Keep state for each node in tree - traverse bottom up,
    # start at the leaves. For each node, remember:
    # - max # of marked nodes in subtree rooted at node
    # - maximum distance to any node in max size set of marked nodes
    maxinsubtree = [-1]*n
    maxdistsubtr = [-1]*n
    
    # Stack-based DFS
    seen = [False] * n
    stack = [0]
    while len(stack) > 0:
        node = stack[-1]
        if not seen[node]:
            # Pre-processing step of DFS
            seen[node] = True
            for child in children[node]:
                stack.append(child)
        else:
            # Post-processing step of DFS
            node = stack.pop()
            
            # Base case: a leaf
            if len(children[node]) == 0:
                maxinsubtree[node] = 1
                maxdistsubtr[node] = 0
            
            # Recursive case: internal node of tree
            else:
                # Merge first with first child, then with rest of children
                fchild = children[node][0]
                marked = maxinsubtree[fchild]
                furthest = maxdistsubtr[fchild] + 1
                if furthest == d:
                    marked += 1
                    furthest = 0
                    
                # Merge other children one by one
                for i in range(1, len(children[node])):
                    child = children[node][i]
                    if furthest + maxdistsubtr[child] + 1 >= d:
                        marked += maxinsubtree[child]
                        furthest = min(furthest, maxdistsubtr[child] + 1)
                    else:
                        marked += maxinsubtree[child] - 1
                        furthest = max(furthest, maxdistsubtr[child] + 1)
                
                maxinsubtree[node] = marked
                maxdistsubtr[node] = furthest

    return maxinsubtree[0]
    
print(catinatree())

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3428 KB Output is correct
2 Correct 25 ms 3428 KB Output is correct
3 Correct 25 ms 3428 KB Output is correct
4 Correct 24 ms 3428 KB Output is correct
5 Correct 26 ms 3384 KB Output is correct
6 Correct 27 ms 3460 KB Output is correct
7 Correct 24 ms 3428 KB Output is correct
8 Correct 25 ms 3428 KB Output is correct
9 Correct 24 ms 3428 KB Output is correct
10 Correct 25 ms 3420 KB Output is correct
11 Correct 25 ms 3428 KB Output is correct
12 Correct 25 ms 3428 KB Output is correct
13 Correct 25 ms 3428 KB Output is correct
14 Correct 25 ms 3428 KB Output is correct
15 Correct 24 ms 3428 KB Output is correct
16 Correct 25 ms 3380 KB Output is correct
17 Correct 24 ms 3420 KB Output is correct
18 Correct 25 ms 3428 KB Output is correct
19 Correct 24 ms 3428 KB Output is correct
20 Correct 25 ms 3428 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3428 KB Output is correct
2 Correct 25 ms 3428 KB Output is correct
3 Correct 25 ms 3428 KB Output is correct
4 Correct 24 ms 3428 KB Output is correct
5 Correct 26 ms 3384 KB Output is correct
6 Correct 27 ms 3460 KB Output is correct
7 Correct 24 ms 3428 KB Output is correct
8 Correct 25 ms 3428 KB Output is correct
9 Correct 24 ms 3428 KB Output is correct
10 Correct 25 ms 3420 KB Output is correct
11 Correct 25 ms 3428 KB Output is correct
12 Correct 25 ms 3428 KB Output is correct
13 Correct 25 ms 3428 KB Output is correct
14 Correct 25 ms 3428 KB Output is correct
15 Correct 24 ms 3428 KB Output is correct
16 Correct 25 ms 3380 KB Output is correct
17 Correct 24 ms 3420 KB Output is correct
18 Correct 25 ms 3428 KB Output is correct
19 Correct 24 ms 3428 KB Output is correct
20 Correct 25 ms 3428 KB Output is correct
21 Correct 30 ms 3684 KB Output is correct
22 Correct 26 ms 3428 KB Output is correct
23 Correct 26 ms 3428 KB Output is correct
24 Correct 26 ms 3420 KB Output is correct
25 Correct 28 ms 3428 KB Output is correct
26 Correct 28 ms 3428 KB Output is correct
27 Correct 30 ms 3428 KB Output is correct
28 Correct 30 ms 3556 KB Output is correct
29 Correct 30 ms 3556 KB Output is correct
30 Correct 30 ms 3428 KB Output is correct
31 Correct 31 ms 3456 KB Output is correct
32 Correct 33 ms 3428 KB Output is correct
33 Correct 29 ms 3420 KB Output is correct
34 Correct 29 ms 3432 KB Output is correct
35 Correct 29 ms 3432 KB Output is correct
36 Correct 29 ms 3560 KB Output is correct
37 Correct 29 ms 3556 KB Output is correct
38 Correct 29 ms 3556 KB Output is correct
39 Correct 33 ms 3548 KB Output is correct
40 Correct 32 ms 3484 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3428 KB Output is correct
2 Correct 25 ms 3428 KB Output is correct
3 Correct 25 ms 3428 KB Output is correct
4 Correct 24 ms 3428 KB Output is correct
5 Correct 26 ms 3384 KB Output is correct
6 Correct 27 ms 3460 KB Output is correct
7 Correct 24 ms 3428 KB Output is correct
8 Correct 25 ms 3428 KB Output is correct
9 Correct 24 ms 3428 KB Output is correct
10 Correct 25 ms 3420 KB Output is correct
11 Correct 25 ms 3428 KB Output is correct
12 Correct 25 ms 3428 KB Output is correct
13 Correct 25 ms 3428 KB Output is correct
14 Correct 25 ms 3428 KB Output is correct
15 Correct 24 ms 3428 KB Output is correct
16 Correct 25 ms 3380 KB Output is correct
17 Correct 24 ms 3420 KB Output is correct
18 Correct 25 ms 3428 KB Output is correct
19 Correct 24 ms 3428 KB Output is correct
20 Correct 25 ms 3428 KB Output is correct
21 Correct 30 ms 3684 KB Output is correct
22 Correct 26 ms 3428 KB Output is correct
23 Correct 26 ms 3428 KB Output is correct
24 Correct 26 ms 3420 KB Output is correct
25 Correct 28 ms 3428 KB Output is correct
26 Correct 28 ms 3428 KB Output is correct
27 Correct 30 ms 3428 KB Output is correct
28 Correct 30 ms 3556 KB Output is correct
29 Correct 30 ms 3556 KB Output is correct
30 Correct 30 ms 3428 KB Output is correct
31 Correct 31 ms 3456 KB Output is correct
32 Correct 33 ms 3428 KB Output is correct
33 Correct 29 ms 3420 KB Output is correct
34 Correct 29 ms 3432 KB Output is correct
35 Correct 29 ms 3432 KB Output is correct
36 Correct 29 ms 3560 KB Output is correct
37 Correct 29 ms 3556 KB Output is correct
38 Correct 29 ms 3556 KB Output is correct
39 Correct 33 ms 3548 KB Output is correct
40 Correct 32 ms 3484 KB Output is correct
41 Correct 648 ms 31992 KB Output is correct
42 Correct 398 ms 17868 KB Output is correct
43 Correct 393 ms 17804 KB Output is correct
44 Correct 397 ms 17888 KB Output is correct
45 Correct 416 ms 17800 KB Output is correct
46 Correct 822 ms 32168 KB Output is correct
47 Correct 817 ms 32320 KB Output is correct
48 Correct 796 ms 32176 KB Output is correct
49 Correct 809 ms 32172 KB Output is correct
50 Correct 384 ms 17120 KB Output is correct
51 Correct 374 ms 17044 KB Output is correct
52 Correct 373 ms 17124 KB Output is correct
53 Correct 753 ms 30796 KB Output is correct
54 Correct 747 ms 30668 KB Output is correct
55 Correct 757 ms 30776 KB Output is correct
56 Correct 34 ms 3680 KB Output is correct
57 Correct 91 ms 7356 KB Output is correct
58 Correct 348 ms 21796 KB Output is correct
59 Correct 783 ms 35188 KB Output is correct
60 Correct 658 ms 32888 KB Output is correct
61 Correct 682 ms 31580 KB Output is correct