제출 #470554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470554		BThero	Fireworks (APIO16_fireworks)	C++17	55 / 100	101 ms	17272 KiB

fireworks

#include <bits/stdc++.h>

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;

const int MAXN = (int)1e5 + 5;

ll h0[MAXN], a0[MAXN];
priority_queue<ll> S[MAXN];
int par[MAXN], edge_len[MAXN];
vector<int> adj[MAXN];
int n, m;

int main() {
    cin >> n >> m;

    for (int i = 2; i <= n + m; i++) {
        cin >> par[i] >> edge_len[i];
        adj[par[i]].push_back(i);
    }

    for (int v = n + m; v > n; v--) {
        h0[v] = edge_len[v];
        a0[v] = -1;
        S[v].push(edge_len[v]);
        S[v].push(edge_len[v]);
    }

    for (int v = n; v > 0; v--) {
        for (int to : adj[v]) {
            h0[v] += h0[to];
            a0[v] += a0[to];

            if (sz(S[to]) > sz(S[v])) {
                S[v].swap(S[to]);
            }

            while (!S[to].empty()) {
                S[v].push(S[to].top());
                S[to].pop();
            }
        }

        while (!S[v].empty() && a0[v] + sz(S[v]) > 1) {
            S[v].pop();
        }
        
        h0[v] += edge_len[v];
        ll P = S[v].top();
        S[v].pop();
        ll Q = S[v].top();
        S[v].pop();
        S[v].push(Q + edge_len[v]);
        S[v].push(P + edge_len[v]);
    }

    vector<ll> slopes;

    while (!S[1].empty()) {
        slopes.push_back(S[1].top());
        S[1].pop();
    }

    reverse(all(slopes));
    ll val = h0[1], slope = a0[1], pos = 0;

    for (ll pt : slopes) {
        val += (pt - pos) * slope;
        pos = pt;
        slope++;
        if (slope == 0) break;
    }

    cout << val << endl;
	return 0;
}

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