Submission #685053

#	Time	Username	Problem	Language	Result	Execution time	Memory
685053		minhnhatnoe	Fireworks (APIO16_fireworks)	C++14	100 / 100	174 ms	63624 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct slope{
    priority_queue<ll> s;
    ll a, b;
    int size(){
        return s.size();
    }
};
vector<vector<int>> g;
vector<slope> dp;
vector<int> c;
void merge_pq(priority_queue<ll> &a, priority_queue<ll> &&b){
    while (b.size()){
        a.push(b.top());
        b.pop();
    }
}
slope merge(vector<slope> &&a, ll c){
    for (int i=1; i<a.size(); i++){
        if (a[i].size() > a[0].size()) swap(a[i], a[0]);
    }
    slope r(move(a[0]));
    for (int i=1; i<a.size(); i++){
        r.a += a[i].a;
        r.b += a[i].b;
        merge_pq(r.s, move(a[i].s));
    }
    while (r.a > 1){
        r.a--;
        r.b += r.s.top();
        r.s.pop();
    }
    ll x = LLONG_MIN;
    if (r.s.size() && r.a >= 0){
        x = r.s.top();
        r.s.pop();
    }
    ll y = LLONG_MIN;
    if (r.s.size() && r.a >= 1){
        y = r.s.top();
        r.s.pop();
    }
    if (x != LLONG_MIN) r.s.push(x + c);
    if (y != LLONG_MIN) r.s.push(y + c);
    r.b -= c;
    return r;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    g.resize(n+m);
    c.resize(n+m);
    dp.resize(n+m);
    for (int i=1; i<n; i++){
        int p; cin >> p >> c[i];
        g[p-1].push_back(i);
    }
    for (int i=n; i<n+m; i++){
        int p; cin >> p >> c[i];
        g[p-1].push_back(i);
        dp[i].a = 1;
        dp[i].b = -c[i];
        dp[i].s.push(c[i]), dp[i].s.push(c[i]);
    }
    for (int i=n-1; i>=0; i--){
        vector<slope> ch;
        for (int u: g[i]){
            ch.emplace_back(move(dp[u]));
        }
        dp[i] = merge(move(ch), c[i]);
    }
    slope r(move(dp[0]));
    if (r.a == 1){
        cout << r.b + r.s.top() << "\n";
    }
    else{
        cout << r.b << "\n";
    }
}

Compilation message (stderr)

fireworks.cpp: In function 'slope merge(std::vector<slope>&&, ll)':
fireworks.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i=1; i<a.size(); i++){
      |                   ~^~~~~~~~~
fireworks.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i=1; i<a.size(); i++){
      |                   ~^~~~~~~~~

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