Submission #154108

#	Time	Username	Problem	Language	Result	Execution time	Memory
154108		mhy908	Fireworks (APIO16_fireworks)	C++14	100 / 100	348 ms	82568 KiB

fireworks

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
int n, m;
vector<int> link[300010];
LL cost[300010];
struct dpfunc
{
    LL sty, sta;
    priority_queue<LL> pq;
    void mergefunc(dpfunc &pl)
    {
        sty+=pl.sty;
        sta+=pl.sta;
        while(!pl.pq.empty()){
            pq.push(pl.pq.top());
            pl.pq.pop();
        }
    }
    void makereal(LL c)
    {
        sty+=c;
        LL zeronum, onenum;
        while(pq.size()>=-sta){
            if(pq.size()==-sta)zeronum=pq.top();
            if(pq.size()==-sta+1)onenum=pq.top();
            pq.pop();
        }
        pq.push(zeronum+c);
        pq.push(onenum+c);
    }
    void init(LL st)
    {
        pq.push(st);
        pq.push(st);
        sty=st;
        sta=-1;
    }
}func[300010];
void get_dp(int num)
{
    if(num>n){
        func[num].init(cost[num]);
        return;
    }
    int maxsize=0, maxnum;
    for(int i=0; i<link[num].size(); i++){
        get_dp(link[num][i]);
        int temp=func[link[num][i]].pq.size();
        if(temp>maxsize){
            maxsize=temp;
            maxnum=i;
        }
    }
    swap(func[link[num][0]], func[link[num][maxnum]]);
    swap(func[num], func[link[num][0]]);
    for(int i=1; i<link[num].size(); i++)
        func[num].mergefunc(func[link[num][i]]);
    func[num].makereal(cost[num]);
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=2; i<=n+m; i++){
        int k;
        scanf("%d %lld", &k, &cost[i]);
        link[k].pb(i);
    }
    get_dp(1);
    while(1){
        if(func[1].pq.size()==-func[1].sta)break;
        func[1].pq.pop();
    }
    func[1].pq.push(0);
    LL p=0;
    while(func[1].pq.size()>=2){
        LL x=func[1].pq.top();
        func[1].pq.pop();
        func[1].sty-=(x-func[1].pq.top())*(++p);
    }
    printf("%lld", func[1].sty);
}

Compilation message (stderr)

fireworks.cpp: In member function 'void dpfunc::makereal(LL)':
fireworks.cpp:25:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pq.size()>=-sta){
               ~~~~~~~~~^~~~~~
fireworks.cpp:26:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pq.size()==-sta)zeronum=pq.top();
                ~~~~~~~~~^~~~~~
fireworks.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pq.size()==-sta+1)onenum=pq.top();
                ~~~~~~~~~^~~~~~~~
fireworks.cpp: In function 'void get_dp(int)':
fireworks.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<link[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
fireworks.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<link[num].size(); i++)
                  ~^~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:72:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(func[1].pq.size()==-func[1].sta)break;
            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fireworks.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld", &k, &cost[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'void get_dp(int)':
fireworks.cpp:31:23: warning: 'onenum' may be used uninitialized in this function [-Wmaybe-uninitialized]
         pq.push(onenum+c);
                 ~~~~~~^~
fireworks.cpp:24:21: note: 'onenum' was declared here
         LL zeronum, onenum;
                     ^~~~~~
fireworks.cpp:30:24: warning: 'zeronum' may be used uninitialized in this function [-Wmaybe-uninitialized]
         pq.push(zeronum+c);
                 ~~~~~~~^~
fireworks.cpp:24:12: note: 'zeronum' was declared here
         LL zeronum, onenum;
            ^~~~~~~
fireworks.cpp:56:51: warning: 'maxnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
     swap(func[link[num][0]], func[link[num][maxnum]]);
                                                   ^

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