Submission #955780

#	Time	Username	Problem	Language	Result	Execution time	Memory
955780		vjudge1	Fireworks (APIO16_fireworks)	C++17	100 / 100	138 ms	66136 KiB

fireworks

#include<bits/stdc++.h>

#define N 300001

int n,M;
int e[N][3],eo,h[N];

std::priority_queue<long long> pq[N];
long long m[N],c[N];

void link(int u,int v,int w) { e[++eo][0]=v,e[eo][1]=w,e[eo][2]=h[u],h[u]=eo; }

void dfs(int u,int p,int ci)
{
    m[u]=c[u]=0;

    if(u > n)
    {
        pq[u].push(ci);
        pq[u].push(ci);
        m[u]=1;
        c[u]=-ci;
        return;
    }

    for(int v,j=h[u];j;j=e[j][2])if((v=e[j][0])-p)
    {
        dfs(v,u,e[j][1]);
        if(pq[v].size()>pq[u].size()) { std::swap(pq[v],pq[u]); std::swap(m[u],m[v]), std::swap(c[u],c[v]); }
        while(pq[v].size()) pq[u].push(pq[v].top()), pq[v].pop();
        m[u]+=m[v];
        c[u]+=c[v];
    }

    if(u!=1)
    {
        while(m[u]>1)
        {
            --m[u];
            c[u]+=pq[u].top();
            pq[u].pop();
        }

        long long x=pq[u].top();
        pq[u].pop();

        long long x2=pq[u].top();
        pq[u].pop();

        pq[u].push(x+ci);
        pq[u].push(x2+ci);

        c[u]-=ci;
    }
    else
    {
        while(m[1]>0)
        {
            --m[1];
            c[1]+=pq[1].top();
            pq[1].pop();
        }
        printf("%lld",c[1]);
    }
}

int main()
{
    scanf("%d%d",&n,&M);
    for(int p,c,i=2;i<=n+M;++i) scanf("%d%d",&p,&c),link(p,i,c);
    dfs(1,1,-1);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d%d",&n,&M);
      |     ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:71:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     for(int p,c,i=2;i<=n+M;++i) scanf("%d%d",&p,&c),link(p,i,c);
      |                                 ~~~~~^~~~~~~~~~~~~~

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