Submission #315956

#	Time	Username	Problem	Language	Result	Execution time	Memory
315956		phathnv	Fireworks (APIO16_fireworks)	C++11	0 / 100	11 ms	14464 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; // slope changing points
    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(){
    cin >> n >> m;
    for(int i = 2; i <= n + m; i++)
        cin >> 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();
    }
    cout << d[1].b;
}

int main(){
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
    readInput();
    solve();
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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