Submission #1190947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190947		raphaelp	Fireworks (APIO16_fireworks)	C++20	100 / 100	209 ms	73000 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
long long dfs(long long x, long long l, vector<vector<pair<long long,long long>>> &AR, priority_queue<long long> &PQ)
{
    priority_queue<long long> temp;
    long long slope =0;
    if (AR[x].size()){
        for (long long i=0; i<AR[x].size(); i++)
        {
            slope+=dfs(AR[x][i].first, AR[x][i].second, AR, temp);
            if (temp.size()>PQ.size())swap(PQ, temp);
            while(!temp.empty())
            {
                PQ.push(temp.top());
                temp.pop();
            }
        }
        while(PQ.size()>slope+1)PQ.pop();
        long long bar1 = PQ.top()+l;
        PQ.pop();
        long long bar0 = PQ.top()+l;
        PQ.pop();
        PQ.push(bar0);
        PQ.push(bar1);
    }
    else
    {
        slope=1;
        PQ.push(l);
        PQ.push(l);
    }
    return slope;
}
int main()
{
    long long N, M;
    cin >> N >> M;
    N+=M;
    long long tot=0;
    vector<vector<pair<long long,long long>>> AR(N);
    for (long long i=1; i<N; i++)
    {
        long long x, d;
        cin >> x >> d;
        tot+=d;
        x--;
        AR[x].push_back({i, d});
    }
    priority_queue<long long> PQ;
    long long ans = dfs(0, 0, AR, PQ);
    PQ.pop();
    long long last = PQ.top();
    for (long long i=0; !PQ.empty(); i++)
    {
        tot-= i * (last-PQ.top());
        last = PQ.top();
        PQ.pop();
    }
    tot-=last*ans;
    cout << tot << endl;
}

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