제출 #315957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315957		phathnv	Fireworks (APIO16_fireworks)	C++11	100 / 100	540 ms	44168 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(){
    readInput();
    solve();
    return 0;
}

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