Submission #558626

#	Time	Username	Problem	Language	Result	Execution time	Memory
558626		Alexandruabcde	Fireworks (APIO16_fireworks)	C++14	55 / 100	2082 ms	95588 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int NMAX = 3e5 + 5;

struct SlopeTrick {
    LL a, b;
    priority_queue <LL> H;

    SlopeTrick () {
        a = 0;
        b = 0;
    }

    SlopeTrick operator += (SlopeTrick r) {
        a += r.a;
        b += r.b;

        while (!r.H.empty()) {
            H.push(r.H.top());
            r.H.pop();
        }

        return *this;
    }
};

int N, M;
int Dad[NMAX];
LL Cost[NMAX];
vector <int> G[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    for (int i = 2; i <= N + M; ++ i ) {
        cin >> Dad[i] >> Cost[i];

        G[Dad[i]].push_back(i);
    }
}

void Solve (int Node, SlopeTrick &ans) {
    while (ans.a > 1) {
        LL x = ans.H.top();
        ans.H.pop();
        -- ans.a;

        ans.b += x;
    }

    LL slope_1 = ans.H.top();
    ans.H.pop();
    LL slope_0 = ans.H.top();
    ans.H.pop();

    ans.H.push(slope_0 + Cost[Node]);
    ans.H.push(slope_1 + Cost[Node]);
    ans.b -= Cost[Node];
}

void Dfs (int Node, SlopeTrick &ans) {
    bool leaf = true;
    for (auto it : G[Node]) {
        SlopeTrick aux;

        leaf = false;
        Dfs(it, aux);

        if (ans.H.size() < aux.H.size())
            swap(ans, aux);
        ans += aux;
    }

    if (leaf) {
        ans.a = 1;
        ans.b = -Cost[Node];
        ans.H.push(Cost[Node]);
        ans.H.push(Cost[Node]);

        return;
    }

    if (Node == 1) return;

    Solve(Node, ans);
}

int main () {
    Read();

    SlopeTrick ans;

    Dfs(1, ans);

    while (ans.a > 0) {
        LL x = ans.H.top();
        ans.H.pop();

        ans.b += x;
        -- ans.a;
    }

    cout << ans.b << '\n';

    return 0;
}

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