Submission #1067002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067002		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	316 ms	56912 KiB

fireworks

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#define ll long long
#define N 300005
#define endl "\n" 
#define fi first
#define se second
using namespace std;

const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
__gnu_pbds::priority_queue<ll> q[N];
ll n,m,w[N],d[N],res=0;
vector<ll>v[N];

void dfs(ll x){
    ll l=0,r=0;
    for(auto y:v[x]){
        dfs(y);
        q[x].join(q[y]);
    }
    if(x<=n){
        for(int i=1;i<d[x];i++)q[x].pop();
        l=q[x].top();q[x].pop();
        r=q[x].top();q[x].pop();
    }
    q[x].push(l+w[x]);
    q[x].push(r+w[x]);
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m;
    for(int i=2,x;i<=n+m;i++){
        cin>>x>>w[i];
        res+=w[i],d[x]++;
        v[x].push_back(i);
    }
    dfs(1);
    q[1].pop();
    ll now=1;
    while(!q[1].empty()){
        res-=q[1].top();
        q[1].pop();
    }
    cout<<res<<endl;
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:43:8: warning: unused variable 'now' [-Wunused-variable]
   43 |     ll now=1;
      |        ^~~

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