oj.uz

Submission #154094

# Submission time Handle Problem Language Result Execution time Memory
154094 2019-09-18T11:08:07 Z arnold518 Fireworks (APIO16_fireworks) C++14
26 / 100
 14 ms 7464 KB 
#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
{
    int slope; ll cut;
    priority_queue<int> PQ;

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

    void propa(int x)
    {
        int i, j;
        int 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<int> 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+(ll)fin->slope*(V[i]-V[i-1]));
        fin->cut+=(ll)fin->slope*(V[i]-V[i-1]);
        fin->slope++;
    }
    printf("%lld", ans);
}

Compilation message

fireworks.cpp: In member function 'void Func::propa(int)':
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:16: note: 'b' was declared here
         int 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:13: note: 'a' was declared here
         int a, b;
             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7288 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 14 ms 7420 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7288 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7420 KB Output is correct
7 Correct 9 ms 7428 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 8 ms 7416 KB Output is correct
13 Correct 8 ms 7420 KB Output is correct
14 Correct 8 ms 7464 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 10 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 10 ms 7416 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7288 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 14 ms 7420 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7288 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 8 ms 7288 KB Output is correct
14 Correct 10 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7420 KB Output is correct
17 Correct 9 ms 7428 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7416 KB Output is correct
20 Correct 8 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Correct 8 ms 7416 KB Output is correct
23 Correct 8 ms 7420 KB Output is correct
24 Correct 8 ms 7464 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Correct 9 ms 7416 KB Output is correct
27 Correct 10 ms 7416 KB Output is correct
28 Correct 8 ms 7416 KB Output is correct
29 Correct 10 ms 7416 KB Output is correct
30 Incorrect 9 ms 7416 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7288 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 14 ms 7420 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7288 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 8 ms 7288 KB Output is correct
14 Correct 10 ms 7416 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7420 KB Output is correct
17 Correct 9 ms 7428 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7416 KB Output is correct
20 Correct 8 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Correct 8 ms 7416 KB Output is correct
23 Correct 8 ms 7420 KB Output is correct
24 Correct 8 ms 7464 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Correct 9 ms 7416 KB Output is correct
27 Correct 10 ms 7416 KB Output is correct
28 Correct 8 ms 7416 KB Output is correct
29 Correct 10 ms 7416 KB Output is correct
30 Incorrect 9 ms 7416 KB Output isn't correct
31 Halted 0 ms 0 KB -