Submission #1020314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020314		vjudge1	Fireworks (APIO16_fireworks)	C++14	100 / 100	224 ms	21612 KiB

fireworks

#include<bits/stdc++.h>//I love Kagamine Rin forever!
#define ll long long
using namespace std;//() is so cute!
struct lmt
{
    ll v[600005];
    int lc[600005],rc[600005],dist[600005];
    lmt(){dist[0]=-1;}
    int merge(int x,int y)
    {
        if(!x||!y)return x+y;
        if(v[y]>v[x])swap(x,y);
        rc[x]=merge(rc[x],y);
        if(dist[lc[x]]<dist[rc[x]])swap(lc[x],rc[x]);
        dist[x]=dist[rc[x]]+1;
        return x;
    }
    int pop(int x)
    {
        return merge(lc[x],rc[x]);
    }
}akari;
int sz;
int rt[600005];

int n,m;
int fa[600005],c[600005];
int deg[600005];
ll ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n+m;i++)
    {
        scanf("%d%d",&fa[i],&c[i]);
        deg[fa[i]]++;
        ans+=c[i];
    }
    for(int i=n+m;i>=2;i--)
    {
        ll l=0,r=0;
        if(i<=n)
        {
            while(--deg[i])rt[i]=akari.pop(rt[i]);
            r=akari.v[rt[i]],rt[i]=akari.pop(rt[i]);
            l=akari.v[rt[i]],rt[i]=akari.pop(rt[i]);
        }
        akari.v[++sz]=l+c[i],akari.v[++sz]=r+c[i];
        rt[i]=akari.merge(rt[i],akari.merge(sz,sz-1));
        rt[fa[i]]=akari.merge(rt[fa[i]],rt[i]);
    }
    while(deg[1]--)rt[1]=akari.pop(rt[1]);
    while(rt[1])ans-=akari.v[rt[1]],rt[1]=akari.pop(rt[1]);
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

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

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