Submission #1097759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097759		Zero_OP	Fireworks (APIO16_fireworks)	C++14	100 / 100	158 ms	85072 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using ld = long double;

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};

template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};

const int MAX = 6e5 + 5;

int n, m;
ll slope[MAX], intercept[MAX];
vector<pair<int, int>> adj[MAX];
priority_queue<ll> pq[MAX];

void convert(int i, ll x){
    while(slope[i] > 1){
        intercept[i] += pq[i].top();
        --slope[i];
        pq[i].pop();
    }

    ll p = pq[i].top(); pq[i].pop();
    ll q = pq[i].top(); pq[i].pop();

    pq[i].push(p + x);
    pq[i].push(q + x);
    intercept[i] -= x;
}

void dfs(int u){
    for(auto [v, w] : adj[u]){
        if(n + 1 <= v && v <= n + m){
            //leaf
            slope[v] = 1;
            intercept[v] = -w;
            pq[v].push(w);
            pq[v].push(w);
        } else{
            //non-leaf
            dfs(v);
            convert(v, w);
        }

        slope[u] += slope[v];
        intercept[u] += intercept[v];
        if(sz(pq[u]) < sz(pq[v])){
            swap(pq[u], pq[v]);
        }

        while(!pq[v].empty()){
            pq[u].push(pq[v].top());
            pq[v].pop();
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    cin >> n >> m;
    for(int i = 2; i <= n + m; ++i){
        int p, w;
        cin >> p >> w;
        adj[p].emplace_back(i, w);
    }

    dfs(1);

    while(slope[1] > 0){
        intercept[1] += pq[1].top();
        --slope[1];
        pq[1].pop();
    }

    cout << intercept[1] << '\n';

    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for(auto [v, w] : adj[u]){
      |              ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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