Submission #502064

#	Time	Username	Problem	Language	Result	Execution time	Memory
502064		blue	Fireworks (APIO16_fireworks)	C++17	100 / 100	335 ms	102412 KiB

fireworks

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define sz(x) int(x.size())

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vi children[1+N];


    vi P(1+N+M);
    vll C(1+N+M);
    for(int i = 2; i <= N+M; i++)
    {
        cin >> P[i] >> C[i];
        children[P[i]].push_back(i);
    }

    C[1] = 0;



    vector< multiset<ll>* > dp(1+N+M);

    vi subtree(1+N+M, 0);
    vi expcount(1+N+M, 0);


    for(int i = N+1; i <= N+M; i++)
    {
        dp[i] = new multiset<ll>;
        dp[i]->insert(C[i]);
        dp[i]->insert(C[i]);

        expcount[i] = 1;
        subtree[i] = 1;
    }

    for(int u = N; u >= 1; u--)
    {
        subtree[u] = 1;
        expcount[u] = 0;

        int max_child = children[u][0];

        for(int v: children[u])
        {
            subtree[u] += subtree[v];
            expcount[u] += expcount[v];

            if(subtree[v] > subtree[max_child]) v = max_child;
        }

        dp[u] = dp[max_child];

        for(int v: children[u])
        {
            if(v == max_child) continue;

            for(ll x: *dp[v]) dp[u]->insert(x);
        }

        while(int(dp[u]->size()) > expcount[u] + 1)
        {
            dp[u]->erase(dp[u]->find(*dp[u]->rbegin()));
        }

        // lp[u] += C[u];

        ll x1 = *dp[u]->rbegin();
        dp[u]->erase(dp[u]->find(x1));

        ll x2 = *dp[u]->rbegin();
        dp[u]->erase(dp[u]->find(x2));

        dp[u]->insert(x1 + C[u]);
        dp[u]->insert(x2 + C[u]);
    }



    dp[1]->erase(dp[1]->find(*dp[1]->rbegin()));

    ll ans = 0;
    for(int i = 2; i <= N+M; i++) ans += C[i];

    ll currx = 0;
    ll currslope = -expcount[1];

    while(!dp[1]->empty())
    {
        ll newx = *dp[1]->begin();
        dp[1]->erase(dp[1]->find(newx));

        ans += (newx - currx) * currslope;

        currslope++;
        currx = newx;
    }

    // while(dp[1].begin() <)

    cout << ans << '\n';
}

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