oj.uz

Submission #651708

# Submission time Handle Problem Language Result Execution time Memory
651708 2022-10-19T21:00:37 Z beaconmc Power Plant (JOI20_power) PyPy 3
0 / 100
 37 ms 18256 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
flag = False

def dfs(a):
    global flag
    
    for i in edges[a]:

        if sus[a-1]==sus[i-1] and sus[i-1]=="1":
            flag = True
        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
if flag:
    print(max(2,ans))
else:
    print(ans)

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18240 KB Output is correct
2 Correct 33 ms 18240 KB Output is correct
3 Correct 36 ms 18192 KB Output is correct
4 Correct 37 ms 18228 KB Output is correct
5 Correct 35 ms 18200 KB Output is correct
6 Correct 34 ms 18256 KB Output is correct
7 Correct 37 ms 18220 KB Output is correct
8 Correct 35 ms 18136 KB Output is correct
9 Correct 34 ms 18176 KB Output is correct
10 Correct 33 ms 18196 KB Output is correct
11 Correct 34 ms 18228 KB Output is correct
12 Correct 35 ms 18132 KB Output is correct
13 Incorrect 33 ms 18200 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18240 KB Output is correct
2 Correct 33 ms 18240 KB Output is correct
3 Correct 36 ms 18192 KB Output is correct
4 Correct 37 ms 18228 KB Output is correct
5 Correct 35 ms 18200 KB Output is correct
6 Correct 34 ms 18256 KB Output is correct
7 Correct 37 ms 18220 KB Output is correct
8 Correct 35 ms 18136 KB Output is correct
9 Correct 34 ms 18176 KB Output is correct
10 Correct 33 ms 18196 KB Output is correct
11 Correct 34 ms 18228 KB Output is correct
12 Correct 35 ms 18132 KB Output is correct
13 Incorrect 33 ms 18200 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18240 KB Output is correct
2 Correct 33 ms 18240 KB Output is correct
3 Correct 36 ms 18192 KB Output is correct
4 Correct 37 ms 18228 KB Output is correct
5 Correct 35 ms 18200 KB Output is correct
6 Correct 34 ms 18256 KB Output is correct
7 Correct 37 ms 18220 KB Output is correct
8 Correct 35 ms 18136 KB Output is correct
9 Correct 34 ms 18176 KB Output is correct
10 Correct 33 ms 18196 KB Output is correct
11 Correct 34 ms 18228 KB Output is correct
12 Correct 35 ms 18132 KB Output is correct
13 Incorrect 33 ms 18200 KB Output isn't correct
14 Halted 0 ms 0 KB -