Submission #960279

#	Time	Username	Problem	Language	Result	Execution time	Memory
960279		sleepntsheep	Fireworks (APIO16_fireworks)	C11	100 / 100	187 ms	56496 KiB

fireworks

#include<stdio.h>

#define N 300001

#define DEFINE_LEFTIST(type, M, is_persistent) \
    int hl_##type[M]; \
    int hr_##type[M]; \
    int hh_##type[M]; \
    type ha_##type[M]; \
    int halc_##type; \
    int leftist_##type(type x) { int p = ++halc_##type; ha_##type[p]=x; hh_##type[p] = 1; hl_##type[p]=hr_##type[p]=0; return p; } \
    int leftist_##type##_copy(int q) {\
        if(!is_persistent)return q; \
        if(!q)return 0;\
        int p=++halc_##type; \
        hl_##type[p]=hl_##type[q]; \
        hr_##type[p]=hr_##type[q]; \
        hh_##type[p]=hh_##type[q]; \
        ha_##type[p]=ha_##type[q]; \
        return p; \
    } \
    int leftist_##type##_merge(int l,int r) \
    { \
        if(!l||!r) { return leftist_##type##_copy(l^r); } \
        if(lt_##type(ha_##type[r],ha_##type[l])) return leftist_##type##_merge(r,l); \
        l=leftist_##type##_copy(l); \
        hr_##type[l]=leftist_##type##_merge(hr_##type[l],r); \
        if(hh_##type[hr_##type[l]] > hh_##type[hl_##type[l]]) { int temp = hr_##type[l]; hr_##type[l] = hl_##type[l], hl_##type[l] = temp; } \
        hh_##type[l] = hh_##type[hr_##type[l]] + 1; \
        return l; \
    } \
    int leftist_##type##_push(int v,type x) { return leftist_##type##_merge(v, leftist_##type(x)); } \
    type leftist_##type##_top(int v) { return ha_##type[v]; } \
    int leftist_##type##_pop(int v) { return leftist_##type##_merge(hl_##type[v], hr_##type[v]); }

typedef long long i64;
int lt_i64(i64 a, i64 b){return a>b;}
DEFINE_LEFTIST(i64, 2000000, 0);

int n,M;
int e[N][3],eo,h[N],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]=leftist_i64_push(pq[u],ci);
        pq[u]=leftist_i64_push(pq[u],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]);
        pq[u]=leftist_i64_merge(pq[u],pq[v]);
        m[u]+=m[v];
        c[u]+=c[v];
    }

    if(u!=1)
    {
        while(m[u]>1)
        {
            --m[u];
            c[u]+=leftist_i64_top(pq[u]);
            pq[u]=leftist_i64_pop(pq[u]);
        }

        long long x=leftist_i64_top(pq[u]);
        pq[u]=leftist_i64_pop(pq[u]);

        long long x2=leftist_i64_top(pq[u]);
        pq[u]=leftist_i64_pop(pq[u]);

        pq[u]=leftist_i64_push(pq[u],x+ci);
        pq[u]=leftist_i64_push(pq[u],x2+ci);

        c[u]-=ci;
    }
    else
    {
        while(m[1]>0)
        {
            --m[1];
            c[1]+=leftist_i64_top(pq[1]);
            pq[1]=leftist_i64_pop(pq[1]);
        }
        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.c: In function 'main':
fireworks.c:103:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d%d",&n,&M);
      |     ^~~~~~~~~~~~~~~~~~~
fireworks.c:104:33: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     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