oj.uz

Submission #651719

# Submission time Handle Problem Language Result Execution time Memory
651719 2022-10-19T21:48:20 Z beaconmc Power Plant (JOI20_power) PyPy 3
47 / 100
 1500 ms 230792 KB 
import sys
#sys.stdin = open("/Users/beaconmc/Downloads/2020-open-power-test-data/in/03-10.txt","r")
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(100000000)


n = int(input())
if n==1:
    print(1)
    quit()
edges = [[] for i in range(n+1)]
par = [-1 for i in range(n+1)]
visited = [False for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
sus = input()

root = 1
flag = False
stack = [root]
visited[root] = True
while stack:
    node = stack.pop()
    for i in edges[node]:
        if not visited[i]:
            par[i] = node
            visited[i] = True
            stack.append(i)


dps = [-1 for i in range(n+1)]
used = [0 for i in range(n+1)]


ans = -1
def dp(a):
    global ans

    if dps[a] != -1:
        return dps[a]
    
    sum = 0
    maxi = 0
    for i in edges[a]:
        if i == par[a]: continue
        sum += dp(i)
        maxi = max(maxi, dp(i))
    
    if sus[a-1]=="1":
        ans = max(ans, maxi+1, sum-1)
    else:
        ans = max(ans,sum)
        
    dps[a] = max(sum-int(sus[a-1]), int(sus[a-1]))
    return dps[a]
        

dp(root)
print(ans)

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18220 KB Output is correct
2 Correct 44 ms 18232 KB Output is correct
3 Correct 48 ms 18152 KB Output is correct
4 Correct 38 ms 18156 KB Output is correct
5 Correct 37 ms 18252 KB Output is correct
6 Correct 34 ms 18188 KB Output is correct
7 Correct 34 ms 18244 KB Output is correct
8 Correct 34 ms 18228 KB Output is correct
9 Correct 34 ms 18220 KB Output is correct
10 Correct 34 ms 18220 KB Output is correct
11 Correct 35 ms 18256 KB Output is correct
12 Correct 36 ms 18216 KB Output is correct
13 Correct 38 ms 18136 KB Output is correct
14 Correct 39 ms 18236 KB Output is correct
15 Correct 35 ms 18136 KB Output is correct
16 Correct 35 ms 18176 KB Output is correct
17 Correct 34 ms 18200 KB Output is correct
18 Correct 35 ms 18252 KB Output is correct
19 Correct 35 ms 18160 KB Output is correct
20 Correct 36 ms 18124 KB Output is correct
21 Correct 36 ms 18176 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18220 KB Output is correct
2 Correct 44 ms 18232 KB Output is correct
3 Correct 48 ms 18152 KB Output is correct
4 Correct 38 ms 18156 KB Output is correct
5 Correct 37 ms 18252 KB Output is correct
6 Correct 34 ms 18188 KB Output is correct
7 Correct 34 ms 18244 KB Output is correct
8 Correct 34 ms 18228 KB Output is correct
9 Correct 34 ms 18220 KB Output is correct
10 Correct 34 ms 18220 KB Output is correct
11 Correct 35 ms 18256 KB Output is correct
12 Correct 36 ms 18216 KB Output is correct
13 Correct 38 ms 18136 KB Output is correct
14 Correct 39 ms 18236 KB Output is correct
15 Correct 35 ms 18136 KB Output is correct
16 Correct 35 ms 18176 KB Output is correct
17 Correct 34 ms 18200 KB Output is correct
18 Correct 35 ms 18252 KB Output is correct
19 Correct 35 ms 18160 KB Output is correct
20 Correct 36 ms 18124 KB Output is correct
21 Correct 36 ms 18176 KB Output is correct
22 Correct 81 ms 22800 KB Output is correct
23 Correct 84 ms 22564 KB Output is correct
24 Correct 94 ms 24284 KB Output is correct
25 Correct 109 ms 22716 KB Output is correct
26 Correct 85 ms 23148 KB Output is correct
27 Correct 81 ms 23752 KB Output is correct
28 Correct 83 ms 23104 KB Output is correct
29 Correct 85 ms 22868 KB Output is correct
30 Correct 90 ms 23408 KB Output is correct
31 Correct 89 ms 22684 KB Output is correct
32 Correct 82 ms 22364 KB Output is correct
33 Correct 95 ms 23836 KB Output is correct
34 Correct 93 ms 23616 KB Output is correct
35 Correct 87 ms 22104 KB Output is correct
36 Correct 80 ms 22336 KB Output is correct
37 Correct 86 ms 21904 KB Output is correct
38 Correct 89 ms 22684 KB Output is correct
39 Correct 82 ms 25620 KB Output is correct
40 Correct 109 ms 34876 KB Output is correct
41 Correct 113 ms 25320 KB Output is correct
42 Correct 87 ms 24216 KB Output is correct
43 Correct 94 ms 26652 KB Output is correct
44 Correct 99 ms 25336 KB Output is correct
45 Correct 107 ms 25244 KB Output is correct
46 Correct 93 ms 27556 KB Output is correct
47 Correct 90 ms 26052 KB Output is correct
48 Correct 81 ms 22684 KB Output is correct
49 Correct 76 ms 22732 KB Output is correct
50 Correct 93 ms 27740 KB Output is correct
51 Correct 109 ms 27288 KB Output is correct
52 Correct 101 ms 24380 KB Output is correct
53 Correct 91 ms 29148 KB Output is correct
54 Correct 80 ms 25064 KB Output is correct
55 Correct 83 ms 22896 KB Output is correct
56 Correct 69 ms 21292 KB Output is correct
57 Correct 81 ms 23992 KB Output is correct
58 Correct 70 ms 21512 KB Output is correct
59 Correct 70 ms 21512 KB Output is correct
60 Correct 83 ms 23720 KB Output is correct
61 Correct 73 ms 21520 KB Output is correct
62 Correct 83 ms 24988 KB Output is correct
63 Correct 83 ms 22356 KB Output is correct

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18220 KB Output is correct
2 Correct 44 ms 18232 KB Output is correct
3 Correct 48 ms 18152 KB Output is correct
4 Correct 38 ms 18156 KB Output is correct
5 Correct 37 ms 18252 KB Output is correct
6 Correct 34 ms 18188 KB Output is correct
7 Correct 34 ms 18244 KB Output is correct
8 Correct 34 ms 18228 KB Output is correct
9 Correct 34 ms 18220 KB Output is correct
10 Correct 34 ms 18220 KB Output is correct
11 Correct 35 ms 18256 KB Output is correct
12 Correct 36 ms 18216 KB Output is correct
13 Correct 38 ms 18136 KB Output is correct
14 Correct 39 ms 18236 KB Output is correct
15 Correct 35 ms 18136 KB Output is correct
16 Correct 35 ms 18176 KB Output is correct
17 Correct 34 ms 18200 KB Output is correct
18 Correct 35 ms 18252 KB Output is correct
19 Correct 35 ms 18160 KB Output is correct
20 Correct 36 ms 18124 KB Output is correct
21 Correct 36 ms 18176 KB Output is correct
22 Correct 81 ms 22800 KB Output is correct
23 Correct 84 ms 22564 KB Output is correct
24 Correct 94 ms 24284 KB Output is correct
25 Correct 109 ms 22716 KB Output is correct
26 Correct 85 ms 23148 KB Output is correct
27 Correct 81 ms 23752 KB Output is correct
28 Correct 83 ms 23104 KB Output is correct
29 Correct 85 ms 22868 KB Output is correct
30 Correct 90 ms 23408 KB Output is correct
31 Correct 89 ms 22684 KB Output is correct
32 Correct 82 ms 22364 KB Output is correct
33 Correct 95 ms 23836 KB Output is correct
34 Correct 93 ms 23616 KB Output is correct
35 Correct 87 ms 22104 KB Output is correct
36 Correct 80 ms 22336 KB Output is correct
37 Correct 86 ms 21904 KB Output is correct
38 Correct 89 ms 22684 KB Output is correct
39 Correct 82 ms 25620 KB Output is correct
40 Correct 109 ms 34876 KB Output is correct
41 Correct 113 ms 25320 KB Output is correct
42 Correct 87 ms 24216 KB Output is correct
43 Correct 94 ms 26652 KB Output is correct
44 Correct 99 ms 25336 KB Output is correct
45 Correct 107 ms 25244 KB Output is correct
46 Correct 93 ms 27556 KB Output is correct
47 Correct 90 ms 26052 KB Output is correct
48 Correct 81 ms 22684 KB Output is correct
49 Correct 76 ms 22732 KB Output is correct
50 Correct 93 ms 27740 KB Output is correct
51 Correct 109 ms 27288 KB Output is correct
52 Correct 101 ms 24380 KB Output is correct
53 Correct 91 ms 29148 KB Output is correct
54 Correct 80 ms 25064 KB Output is correct
55 Correct 83 ms 22896 KB Output is correct
56 Correct 69 ms 21292 KB Output is correct
57 Correct 81 ms 23992 KB Output is correct
58 Correct 70 ms 21512 KB Output is correct
59 Correct 70 ms 21512 KB Output is correct
60 Correct 83 ms 23720 KB Output is correct
61 Correct 73 ms 21520 KB Output is correct
62 Correct 83 ms 24988 KB Output is correct
63 Correct 83 ms 22356 KB Output is correct
64 Correct 625 ms 59308 KB Output is correct
65 Correct 623 ms 58656 KB Output is correct
66 Correct 684 ms 59044 KB Output is correct
67 Correct 622 ms 59204 KB Output is correct
68 Correct 648 ms 62476 KB Output is correct
69 Correct 622 ms 62488 KB Output is correct
70 Correct 654 ms 62328 KB Output is correct
71 Correct 650 ms 59904 KB Output is correct
72 Correct 608 ms 58104 KB Output is correct
73 Execution timed out 1587 ms 230792 KB Time limit exceeded
74 Halted 0 ms 0 KB -