Submission #380513

#	Time	Username	Problem	Language	Result	Execution time	Memory
380513		solaimanope	Fireworks (APIO16_fireworks)	C++17	100 / 100	231 ms	53084 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 3e5+7;
vector< int >children[MAXN];
int parent[MAXN];
int weight[MAXN];

struct SlopeTrickable {
    priority_queue< LL >slopeChanges;
    LL m, c; ///mx + c is the rightmost line

    void throwSlopesGreaterThan(LL g) {
        while (m > g) {
            ///mx + c = (m-1)x + (x+c)
            m -= 1;
            c += slopeChanges.top();
            slopeChanges.pop();
        }
    }
};

void merge(SlopeTrickable &from, SlopeTrickable &to) {
    if (from.slopeChanges.size() > to.slopeChanges.size())
        swap(from, to);

    while (!from.slopeChanges.empty()) {
        to.slopeChanges.push(from.slopeChanges.top());
        from.slopeChanges.pop();
    }

    to.m += from.m;
    to.c += from.c;
}

SlopeTrickable subtree[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= n+m; i++) {
        cin >> parent[i] >> weight[i];
        children[parent[i]].push_back(i);
    }

    for (int i = n+1; i <= n+m; i++) {
        subtree[i].slopeChanges.push(weight[i]);
        subtree[i].slopeChanges.push(weight[i]);
        subtree[i].m = 1;
        subtree[i].c = -weight[i];
    }

    for (int i = n; i > 0; i--) {
        for (int c : children[i]) {
            merge(subtree[c], subtree[i]);
        }
        subtree[i].throwSlopesGreaterThan(1);

        if (i > 1) {
            LL x1 = subtree[i].slopeChanges.top();
            subtree[i].slopeChanges.pop();
            LL x0 = subtree[i].slopeChanges.top();
            subtree[i].slopeChanges.pop();

            subtree[i].slopeChanges.push(x0+weight[i]);
            subtree[i].slopeChanges.push(x1+weight[i]);
            subtree[i].c -= weight[i];
        }
    }

    cout << subtree[1].slopeChanges.top() + subtree[1].c << "\n";

    return 0;
}

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