Submission #315954

#	Time	Username	Problem	Language	Result	Execution time	Memory
315954		phathnv	Fireworks (APIO16_fireworks)	C++11	19 / 100	11 ms	14592 KiB

fireworks

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "FIREWORKS"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 3e5 + 1;
const ll INF = 5e14;

struct data{
    ll a, b;
    priority_queue <ll> pq;
    void operator += (data &other){
        a += other.a;
        b += other.b;
        if (pq.size() < other.pq.size())
            swap(pq, other.pq);
        while (!other.pq.empty()){
            pq.push(other.pq.top());
            other.pq.pop();
        }
    }
};

int n, m, p[N], c[N];
data d[N];

void readInput(){
    scanf("%d %d", &n, &m);
    for(int i = 2; i <= n + m; i++)
        scanf("%d %d", &p[i], &c[i]);
}

void solve(){
    for(int i = 1; i <= n; i++){
        d[i].a = 0;
        d[i].b = 0;
    }
    for(int i = n + 1; i <= n + m; i++){
        d[i].a = 1;
        d[i].b = -c[i];
        d[i].pq.push(c[i]);
        d[i].pq.push(c[i]);
        d[p[i]] += d[i];
    }
    for(int i = n; i > 1; i--){
        while (d[i].a > 1){
            d[i].a--;
            d[i].b += d[i].pq.top();
            d[i].pq.pop();
        }

        ll p1 = d[i].pq.top();
        d[i].pq.pop();
        ll p0 = d[i].pq.top();
        d[i].pq.pop();
        d[i].pq.push(p0 + c[i]);
        d[i].pq.push(p1 + c[i]);

        d[i].b -= c[i];
        d[p[i]] += d[i];
    }
    while (d[1].a > 0){
        d[1].a--;
        d[1].b += d[1].pq.top();
        d[1].pq.pop();
    }
    printf("%I64d", d[1].b);
}

int main(){
    readInput();
    solve();
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void solve()':
fireworks.cpp:74:17: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   74 |     printf("%I64d", d[1].b);
      |             ~~~~^   ~~~~~~
      |                 |        |
      |                 int      ll {aka long long int}
      |             %I64lld
fireworks.cpp: In function 'void readInput()':
fireworks.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |         scanf("%d %d", &p[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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