Submission #1092152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092152		ASN49K	Fireworks (APIO16_fireworks)	C++14	100 / 100	315 ms	98136 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const int N=3e5;
vector<pair<int,int>>g[N];
multiset<i64>mp[N];
i64 rez[N];
void dfs(int nod)
{
    if(g[nod].size()==0)
    {
        mp[nod].insert(0);
        mp[nod].insert(0);
        return;
    }
    for(auto &c:g[nod])
    {
        dfs(c.first);
        i64 v1=*mp[c.first].rbegin();
        mp[c.first].erase(mp[c.first].find(v1));
        i64 v2=*mp[c.first].rbegin();
        mp[c.first].erase(mp[c.first].find(v2));

        mp[c.first].insert(v1+c.second);
        mp[c.first].insert(v2+c.second);


        if(mp[nod].size() < mp[c.first].size())
        {
            swap(mp[nod] , mp[c.first]);
        }
        for(auto &v:mp[c.first])
        {
            mp[nod].insert(v);
        }
    }
    for(int i=1;i<(int)g[nod].size();i++)
    {
        mp[nod].erase(mp[nod].find(*mp[nod].rbegin()));
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    n+=m;

    i64 rez=0;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        rez+=y;
        x--;
        g[x].pb({i,y});
    }
    dfs(0);
    i64 last=0;
    for(int i=m;i>0;i--)
    {
        i64 it=*mp[0].begin();
        mp[0].erase(mp[0].find(it));
        rez+=(last-it)*i;
        last=it;
    }
    cout<<rez;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

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