Submission #154097

#	Time	Username	Problem	Language	Result	Execution time	Memory
154097		arnold518	Fireworks (APIO16_fireworks)	C++14	100 / 100	319 ms	74492 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M, C[MAXN+10];
vector<int> adj[MAXN+10];
ll ans=1e18;

struct Func
{
    ll slope, cut;
    priority_queue<ll> PQ;

    Func() : slope(0), cut(0) {}

    void propa(ll x)
    {
        int i, j;
        ll a, b;
        while(!PQ.empty() && slope+(int)PQ.size()>-1)
        {
            if(slope+PQ.size()==0) a=PQ.top();
            if(slope+PQ.size()==1) b=PQ.top();
            PQ.pop();
        }
        PQ.push(a+x); PQ.push(b+x);
        cut+=x;
    }
};

Func *dfs(int now)
{
    int i, j;
    Func *ret=new Func;
    if(adj[now].empty())
    {
        ret->slope=-1;
        ret->cut=C[now];
        ret->PQ.push(C[now]);
        ret->PQ.push(C[now]);
        return ret;
    }

    for(int nxt : adj[now])
    {
        Func *t=dfs(nxt);
        if(t->PQ.size()>ret->PQ.size()) swap(t, ret);
        ret->slope+=t->slope; ret->cut+=t->cut;
        while(!t->PQ.empty()) ret->PQ.push(t->PQ.top()), t->PQ.pop();
    }

    if(now!=1) ret->propa(C[now]);
    return ret;
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=2; i<=N+M; i++)
    {
        int p;
        scanf("%d%d", &p, &C[i]);
        adj[p].push_back(i);
    }

    Func *fin=dfs(1);
    vector<ll> V;
    while(!fin->PQ.empty()) V.push_back(fin->PQ.top()), fin->PQ.pop(); V.push_back(0);
    reverse(V.begin(), V.end());

    for(i=1; i<V.size(); i++)
    {
        ans=min(ans, fin->cut+fin->slope*(V[i]-V[i-1]));
        fin->cut+=fin->slope*(V[i]-V[i-1]);
        fin->slope++;
    }
    printf("%lld", ans);
}

Compilation message (stderr)

fireworks.cpp: In member function 'void Func::propa(ll)':
fireworks.cpp:23:13: warning: unused variable 'i' [-Wunused-variable]
         int i, j;
             ^
fireworks.cpp:23:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
fireworks.cpp: In function 'Func* dfs(int)':
fireworks.cpp:38:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
fireworks.cpp:38:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:75:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     while(!fin->PQ.empty()) V.push_back(fin->PQ.top()), fin->PQ.pop(); V.push_back(0);
     ^~~~~
fireworks.cpp:75:72: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
     while(!fin->PQ.empty()) V.push_back(fin->PQ.top()), fin->PQ.pop(); V.push_back(0);
                                                                        ^
fireworks.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<V.size(); i++)
              ~^~~~~~~~~
fireworks.cpp:63:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
fireworks.cpp:65: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:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &p, &C[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'Func* dfs(int)':
fireworks.cpp:31:32: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
         PQ.push(a+x); PQ.push(b+x);
                               ~^~
fireworks.cpp:24:15: note: 'b' was declared here
         ll a, b;
               ^
fireworks.cpp:31:18: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
         PQ.push(a+x); PQ.push(b+x);
                 ~^~
fireworks.cpp:24:12: note: 'a' was declared here
         ll a, b;
            ^

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