Submission #1246821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246821		ofoz	Jobs (BOI24_jobs)	Pypy 3	11 / 100	865 ms	545980 KiB

Main

from sys import setrecursionlimit
from math import sqrt, floor
from collections import deque

setrecursionlimit(int(3e5)+5)
def solve():
    n, s = map(int, input().split(" "))
    adj = [[] for _ in range(n+1)]
    w = [0] * (n+1)
    roots = []
    for i in range(1, n+1):
        x, v = map(int, input().split(" "))
        if v: adj[v].append(i)
        else: roots.append(i)
        w[i] = x

    vis = [0] * (n+1)
    def dp(v: int):
        res = w[v]
        for to in adj[v]:
            res += max(0, dp(to))
        return res

    res = 0

    for v in roots: res += max(0, dp(v))
    print(res)

"""

"""
test = 0
for _ in range(1 if not test else int(input())): solve()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 37%)

=======

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31