Submission #1246839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246839		ofoz	Jobs (BOI24_jobs)	Pypy 3	0 / 100	279 ms	83876 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)
    cur = []
    def dfs(v: int):
        nonlocal cur
        cur.append(w[v])
        if adj[v]: dfs(adj[v][0])


    res = 0

    for v in roots:
        dfs(v)
        mx = 0
        sm = 0
        for x in cur:
            sm += x
            if sm < -s: break
            mx = max(mx, sm)
        res += mx


    print(res)

"""
keep track of the maximum profit we have achieved
once our current profit is less than -s, we can just return the max profit achieved
"""
test = 0
for _ in range(1 if not test else int(input())): solve()

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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