Submission #1223033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223033		Szymon_Pilipczuk	Fireworks (APIO16_fireworks)	C++20	7 / 100	0 ms	328 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<vector<int>> gr;
vector<int> l;
vector<ll> mod;
vector<priority_queue<ll>> pq;
vector<ll> ans;
int comb(vector<int> v,int cmod)
{
    int n = v.size();
    vector<int> c;
    pair<int,int> mx = {0,-1};
    ll mx2 = -1;
    for(int i : v)
    {
        if(pq[i].size() > mx.st)
        {
            mx = {pq[i].size(),i};
        }
        mx2 = max(mx2,pq[i].top()+mod[i]);
    }
    int r = mx.nd;
    ll sum = 0;
    for(int i : v)
    {
        if(r != i)
        {
            c.pb(i);
        }
        sum += ans[i] + mx2-(pq[i].top()+mod[i]);
    }
    for(int i : c)
    {
        while(!pq[i].empty())
        {
            pq[r].push((pq[i].top()+mod[i]-mod[r]));
            pq[i].pop();
        }
    }
    rep(i,n-1)
    {
        ll a = pq[r].top();
        pq[r].pop();
        sum -= (a-pq[r].top()) * (n-1-i);
    }
    ans[r] = sum;
    mod[r] -= cmod;
    ll b = pq[r].top();
    pq[r].pop();
    ll a = pq[r].top();
    pq[r].pop();
    pq[r].push(a+cmod);
    pq[r].push(b+cmod);
    return r;
}
int n,m;
int dfs(int v)
{
    if(gr[v].size() > 0)
    {
        vector<int> cu;
        for(int i : gr[v])
        {
            cu.pb(dfs(i));
        }
        return comb(cu,l[v]);
    }
    else
    {
        int c = v-n;
        pq[c].push(l[v]);
        pq[c].push(l[v]);
        mod[c] = 0;
        ans[c] = 0;
        return c;
    }
}
int main()
{
    cin>>n>>m;
    gr.resize(n+m);
    l.resize(n+m);
    l[0] = 0;
    for(int i = 1;i<n+m;i++)
    {
        int p,c;
        cin>>p>>c;
        p--;
        gr[p].pb(i);
        l[i] = c;
    }
    ans.resize(m);
    mod.resize(m);
    pq.resize(m);
    cout<<ans[dfs(0)]<<"\n";
}

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