oj.uz

Submission #651718

# Submission time Handle Problem Language Result Execution time Memory
651718 2022-10-19T21:47:07 Z beaconmc Power Plant (JOI20_power) PyPy 3
0 / 100
 1149 ms 524288 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] = a
            visited[i] = True
            stack.append(i)


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

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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18156 KB Output is correct
2 Runtime error 1149 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18156 KB Output is correct
2 Runtime error 1149 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18156 KB Output is correct
2 Runtime error 1149 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -