제출 #1223038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223038		Szymon_Pilipczuk	Fireworks (APIO16_fireworks)	C++20	100 / 100	215 ms	64916 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<priority_queue<ll>> pq;
vector<ll> ans;
int comb(vector<int> v,int cmod)
{
    int n = v.size();
    vector<int> c;
    pair<ll,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());
    }
    int r = mx.nd;
    ll sum = 0;
    for(int i : v)
    {
        if(r != i)
        {
            c.pb(i);
        }
        sum += ans[i] + mx2-(pq[i].top());
    }
    for(int i : c)
    {
        while(!pq[i].empty())
        {
            pq[r].push((pq[i].top()));
            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;
    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]);
        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);
    pq.resize(m);
    cout<<ans[dfs(0)]<<"\n";
}

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