Submission #1315381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315381		vnedu	Fireworks (APIO16_fireworks)	C++17	100 / 100	213 ms	68472 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#define TASK "light"

const int N = 3e5 + 5;
int n,m;
long long sum=0;
vector<pair<int,int>> adj[N];
multiset<long long> f[N];
void dfs(int u, int pa, int l)
{
//    cout<<u<<' '<<pa<<'\n';
    if(u>n)
    {
        f[u].insert(l);
        f[u].insert(l);
        return;
    }
    for(pair<int,int> p : adj[u])
    {
        int v=p.first,len=p.second;
        if(v!=pa)
        {
            dfs(v,u,len);
            if((int)f[u].size()<(int)f[v].size())
            {
                f[v].insert(f[u].begin(),f[u].end());
                f[u].clear();
                swap(f[u],f[v]);
            }
            else
            {
                f[u].insert(f[v].begin(),f[v].end());
                f[v].clear();
            }
        }
    }
//    cout<<u<<' '<<(int)adj[u].size()-1<<'\n';
//    for(long long pos : f[u]) cout<<pos<<' ';
//    cout<<'\n';
    if(u!=1)
    {
        long long slope=(int)adj[u].size()-1-1;
        long long ammot=0,khong=0;
        while(1)
        {
            if(f[u].empty() || slope<=-2) break;
            long long r=*(--(f[u].end())),l;
            f[u].erase(--(f[u].end()));
            if(f[u].empty()) l=0;
            else l=*(--(f[u].end()));
            if(slope==-1) ammot=r-l;
            if(slope==0) khong=r-l;
            --slope;
        }
        long long curPos;
        if(f[u].empty()) curPos=0;
        else curPos=*(--(f[u].end()));
        curPos+=ammot+l;
        if(curPos) f[u].insert(curPos);
        curPos+=khong;
        if(curPos) f[u].insert(curPos);
    }
    else
    {
        int slope=(int)adj[u].size();
        int firstSlope=slope-(int)f[u].size();
//        cout<<sum<<' '<<firstSlope<<' '<<slope<<'\n';
        if(firstSlope>0) cout<<sum;
        else
        {
            while(slope>1)
            {
                --slope;
                f[u].erase(--(f[u].end()));
            }
            long long opt=*(--(f[u].end()));
            sum+=firstSlope*opt;
            for(long long pos : f[u]) sum+=opt-pos;
            cout<<sum;
        }
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=2;i<=n+m;++i)
    {
        int p,l;
        cin>>p>>l;
        sum+=l;
        adj[i].push_back({p,l});
        adj[p].push_back({i,l});
    }
    dfs(1,0,0);
}

int main(void)
{
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int testcase=1;
//    cin>>testcase;

    while(testcase--)
        solve();

    return 0;
}

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