제출 #558628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558628		Alexandruabcde	Fireworks (APIO16_fireworks)	C++14	100 / 100	245 ms	71872 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;
        H = new priority_queue<LL>;
    }

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

        if (H->size() < r.H->size())
            swap(H, r.H);

        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);
        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: 45 / 45