Submission #1009377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009377		imarn	Fireworks (APIO16_fireworks)	C++14	100 / 100	155 ms	87416 KiB

fireworks

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
using namespace std;
const int mxn=3e5+5;
vector<int>g[mxn];
ll p[mxn],c[mxn],n;
priority_queue<ll>q[mxn];
ll a[mxn]{0};ll b[mxn]{0};
void dfs(int u){
    for(auto v:g[u]){
        if(v>n)continue;
        dfs(v);
        while(a[v]>1){
            a[v]--;
            b[v]+=q[v].top();q[v].pop();
        }
        ll x=q[v].top();q[v].pop();
        ll y=q[v].top();q[v].pop();
        q[v].push(x+c[v]);q[v].push(y+c[v]);
        b[v]-=c[v];
        if(q[v].size()>q[u].size())swap(q[u],q[v]);
        while(!q[v].empty())q[u].push(q[v].top()),q[v].pop();
        a[u]+=a[v];b[u]+=b[v];
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;cin>>n>>m;
    for(int i=2;i<=n+m;i++)cin>>p[i]>>c[i],g[p[i]].pb(i);
    for(int i=n+1;i<=n+m;i++){
        q[p[i]].push(c[i]);q[p[i]].push(c[i]);
        b[p[i]]-=c[i];a[p[i]]++;
    }dfs(1);
    while(a[1]>0){
        a[1]--;b[1]+=q[1].top();q[1].pop();
    }cout<<b[1];
}

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