Submission #154105

#	Time	Username	Problem	Language	Result	Execution time	Memory
154105		mhy908	Fireworks (APIO16_fireworks)	C++14	100 / 100	391 ms	85056 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(1){
            if(pq.size()==-sta-1)break;
            if(pq.size()==-sta)zeronum=pq.top();
            if(pq.size()==-sta+1)onenum=pq.top();
            pq.pop();
        }
        zeronum+=c;
        onenum+=c;
        pq.push(zeronum);
        pq.push(onenum);
    }
    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){
        p++;
        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:26:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pq.size()==-sta-1)break;
                ~~~~~~~~~^~~~~~~~
fireworks.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pq.size()==-sta)zeronum=pq.top();
                ~~~~~~~~~^~~~~~
fireworks.cpp:28: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:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<link[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
fireworks.cpp:61: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:75:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(func[1].pq.size()==-func[1].sta)break;
            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fireworks.cpp:67: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:70: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:59: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