Submission #349291

#	Time	Username	Problem	Language	Result	Execution time	Memory
349291		denkendoemeer	Fireworks (APIO16_fireworks)	C++14	100 / 100	293 ms	63892 KiB

fireworks

#include<bits/stdc++.h>
#define ll long long
using namespace std;
priority_queue<ll>pq[300005];
vector<ll>g[300005];
ll sz[300005],cost[300005];
void merg(ll x,ll y)
{
    if (pq[x].size()<pq[y].size())
        swap(pq[x],pq[y]);
    while(!pq[y].empty()){
        pq[x].push(pq[y].top());
        pq[y].pop();
    }
    sz[x]+=sz[y];
}
void dfs(ll nod)
{
    ll x,y,sum=0;
    sz[nod]=cost[nod];
    for(auto &it:g[nod]){
        dfs(it);
        sum++;
        merg(nod,it);
    }
    if (sum==0){
        pq[nod].push(cost[nod]);
        pq[nod].push(cost[nod]);
    }
    else{
        while(sum>1)
            pq[nod].pop(),sum--;
        x=pq[nod].top();
        pq[nod].pop();
        y=pq[nod].top();
        pq[nod].pop();
        pq[nod].push(x+cost[nod]);
        pq[nod].push(y+cost[nod]);
    }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll n,m,x,i;
    scanf("%lld%lld",&n,&m);
    for(i=2;i<=n+m;i++){
        scanf("%lld%lld",&x,&cost[i]);
        g[x].push_back(i);
    }
    dfs(1);
    x=pq[1].top();
    pq[1].pop();
    pq[1].push(0);
    ll num=0,ans=0;
    while(!pq[1].empty()){
        ans=ans+num*(x-pq[1].top());
        x=pq[1].top();
        pq[1].pop();
        num--;
    }
    printf("%lld\n",sz[1]+ans);
return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
fireworks.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |         scanf("%lld%lld",&x,&cost[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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