Submission #714530

#	Time	Username	Problem	Language	Result	Execution time	Memory
714530		Spade1	Fireworks (APIO16_fireworks)	C++14	7 / 100	16 ms	26268 KiB

fireworks

#include<bits/stdc++.h>
//#include <grader.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int N = 3e5 + 10;

vector<pll> adj[N];
priority_queue<ll> L[N];
priority_queue<ll, vector<ll>, greater<ll>> R[N];
ll ans[N];

void add(int i, int a, int b) {
    if (!L[i].empty() && a >= L[i].top()) {
        R[i].push(a); R[i].push(b);
        L[i].push(R[i].top()); R[i].pop();
        ans[i] += a-L[i].top();
    }
    else {
        L[i].push(a); L[i].push(b);
        R[i].push(L[i].top()); L[i].pop();
        ans[i] += R[i].top()-b;
    }
}

void dfs(int i) {
    if (adj[i].empty()) {
        L[i].push(0);
        R[i].push(0);
        ans[i] = 0;
        return;
    }
    for (auto [j, w] : adj[i]) {
        dfs(j);
        ans[i] += ans[j];
        int a = L[j].top() + w;
        int b = R[j].top() + w;
        add(i, a, b);
    }
    ll save;
    save = L[i].top();
    while (!L[i].empty()) L[i].pop();
    L[i].push(save);
    save = R[i].top();
    while (!R[i].empty()) R[i].pop();
    R[i].push(save);
}

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 2; i <= n+m; ++i) {
        ll p, c; cin >> p >> c;
        adj[p].pb({i, c});
    }
    dfs(1);
    cout << ans[1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [j, w] : adj[i]) {
      |               ^

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