Submission #1246885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246885		ofoz	Jobs (BOI24_jobs)	Pypy 3	14 / 100	1246 ms	1114112 KiB

Main

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

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


    cur = []
    newAdj = [[] for _ in range(2*n+2)]
    def dfs(v: int, p: int, cur: int, mn: int):

        nonlocal w, adj
        if cur + w[v] >= 0:
            newAdj[p].append((v, -mn, cur + w[v]))
            cur = 0
            mn = 0

            p = v
            
        else:
            cur += w[v]
            mn = min(mn, cur)

        for to in adj[v]:
            dfs(to, p, cur, mn)


    res = 0
    p = n+1
    newRoots = []
    for v in roots:
        dfs(v, p, 0, 0)
        newRoots.append(p)
        p += 1
    
    cur = s
    pq = []
    heapq.heapify(pq)
    for v in newRoots:
        for (v, mn, P) in newAdj[v]:
            heapq.heappush(pq, (mn, v, P))


    while pq:
        mn, v, P = pq[0]
        heapq.heappop(pq)
        
        if mn > cur: break
        cur += P

        for (to, mn, P) in newAdj[v]:
            heapq.heappush(pq, (mn, to, P))


    print(cur - s)



"""
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

maybe create another graph?
obviously, if we take a path with a negative value, we should keep taking the edges until we get a profit, otherwise it doesnt make sense to take them
this means we can compress the graph into another graph G' where each edge is a path with negative profit, but which leads to a node with higher value.
we can, then, just always traverse the edge with lowest weight

lets traverse the tree and maintain the parent node p of the graph G' for each node. once we encounter positive profit, we will append an edge to p that
goes to v, whose value is the lowest value encountered in the path
"""
test = 0
for _ in range(1 if not test else int(input())): solve()

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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