Submission #209723

#	Time	Username	Problem	Language	Result	Execution time	Memory
209723		jh05013	Fireworks (APIO16_fireworks)	Pypy 2	100 / 100	1494 ms	171680 KiB

fireworks

from heapq import *
class Maxheap:
    def __init__(_): _.h = []
    def add(_, v): heappush(_.h, -v)
    def top(_): return -_.h[0] if _.h else -10**18
    def pop(_): return -heappop(_.h)

class Graph:
    def __init__(_):
        _.change = Maxheap() # increment slope at ...
        _.a = _.y = 0 # last line has slope a, starts from y
        _.dx = 0      # the whole graph is shifted right by ...
    def __iadd__(s, o):
        if len(s.change.h) < len(o.change.h): s,o = o,s
        dx = s.change.top() - o.change.top()
        s.a, s.y = s.a+o.a, s.y+o.y+(o.a*dx if dx>=0 else -s.a*dx)
        for v in o.change.h: s.change.add(-v + o.dx-s.dx)
        return s
    
    def shiftx(_, v): _.dx+= v
    def shifty(_, v): _.y+= v
    def addleft(_, v):
        if _.change.top() < v-_.dx:
            dx = v-_.dx - _.change.top()
            _.y+= _.a*dx
        _.change.add(v-_.dx)
    def addright(_, v):
        if _.change.top() < v-_.dx:
            dx = v-_.dx - _.change.top()
            _.y+= _.a*dx; _.a+= 1
            _.change.add(v-_.dx)
            return
        _.change.add(v-_.dx)
        _.a+= 1; _.y+= _.change.top()-(v-_.dx)
    def cutright(_):
        v = _.change.pop(); rval = v+_.dx
        dx = v-_.change.top()
        _.a-= 1; _.y-= _.a*dx
        return rval

input = __import__('sys').stdin.readline
range = xrange
MIS = lambda: map(int,input().split())

n = sum(MIS())
C = [0, 0]
adj = [[] for i in range(n+1)]
adj[0].append(1)
for i in range(n-1):
    p, c = MIS()
    C.append(c)
    adj[p].append(i+2)

# dfs because python bad at recursion
dfsord = []
stack = [0]
while stack:
    p = stack.pop()
    for q in adj[p]: dfsord.append(q); stack.append(q)
del stack

# slope trick
graph = [None for i in range(n+2)]
for v in reversed(dfsord):
    G = Graph()
    if not adj[v]:
        G.addleft(C[v])
        G.addright(C[v])
        graph[v] = G
        continue
    for u in adj[v]: G+= graph[u]
    while G.a > 1: G.cutright()
    s1 = G.change.pop()
    s2 = G.change.pop()
    G.change.add(s1+C[v])
    G.change.add(s2+C[v])
    graph[v] = G
print(G.y)

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45