oj.uz

Submission #651707

# Submission time Handle Problem Language Result Execution time Memory
651707 2022-10-19T20:55:50 Z beaconmc Power Plant (JOI20_power) PyPy 3
0 / 100
 39 ms 18232 KB 
import sys
sys.setrecursionlimit(1000000000)


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()

for i in range(1,n+1):
    if len(edges[i]) == 1:
        root = i

def dfs(a):
    for i in edges[a]:
        if not visited[i]:
            par[i] = a
            visited[i] = True
            dfs(i)
visited[root] = True
dfs(root)
dps = [-1 for i in range(n+1)]
used = [0 for i in range(n+1)]

def dp(a):

    if dps[a] != -1:
        return dps[a]
    if sus[a-1]=="0":
        
        sums = 0
        for i in edges[a]:
            if i == par[a]: continue
            sums += dp(i)
        dps[a] = sums
        
        return sums

    dps[a] = 1
    maxi = 0
    for i in edges[a]:
        if i == par[a]: continue
        maxi += dp(i)

    if dps[a] <= maxi-1:
        used[a] = 1
    dps[a] = max(dps[a], maxi-1)
    return dps[a]

ans = dp(root)
if used[root]:
    ans += 2
elif sus[root-1]=="1":
    ans += 1
print(ans)

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Correct 34 ms 18180 KB Output is correct
3 Correct 33 ms 18232 KB Output is correct
4 Correct 33 ms 18196 KB Output is correct
5 Correct 39 ms 18220 KB Output is correct
6 Correct 35 ms 18220 KB Output is correct
7 Correct 37 ms 18224 KB Output is correct
8 Correct 37 ms 18232 KB Output is correct
9 Correct 36 ms 18228 KB Output is correct
10 Incorrect 33 ms 18188 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Correct 34 ms 18180 KB Output is correct
3 Correct 33 ms 18232 KB Output is correct
4 Correct 33 ms 18196 KB Output is correct
5 Correct 39 ms 18220 KB Output is correct
6 Correct 35 ms 18220 KB Output is correct
7 Correct 37 ms 18224 KB Output is correct
8 Correct 37 ms 18232 KB Output is correct
9 Correct 36 ms 18228 KB Output is correct
10 Incorrect 33 ms 18188 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Correct 34 ms 18180 KB Output is correct
3 Correct 33 ms 18232 KB Output is correct
4 Correct 33 ms 18196 KB Output is correct
5 Correct 39 ms 18220 KB Output is correct
6 Correct 35 ms 18220 KB Output is correct
7 Correct 37 ms 18224 KB Output is correct
8 Correct 37 ms 18232 KB Output is correct
9 Correct 36 ms 18228 KB Output is correct
10 Incorrect 33 ms 18188 KB Output isn't correct
11 Halted 0 ms 0 KB -