제출 #470551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470551		BThero	Fireworks (APIO16_fireworks)	C++17	55 / 100	1917 ms	23852 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;

struct dp_t {
    ll h0, a0;
    multiset<ll> S;

    dp_t() {
        h0 = a0 = 0;
    }

    ll get(ll x) {
        ll val = h0;
        ll slope = a0;
        ll pos = 0;

        for (ll pt : S) {
            if (pt >= x) {
                break;
            }

            val += slope * (pt - pos);
            pos = pt;
            slope++;
        }

        val += (x - pos) * slope;
        return val;
    }
} dp[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--) {
        dp[v].h0 = edge_len[v];
        dp[v].a0 = -1;
        dp[v].S.insert(edge_len[v]);
        dp[v].S.insert(edge_len[v]);
    }

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

            for (ll pt : dp[to].S) {
                dp[v].S.insert(pt);
            }

            dp[to].S.clear();
        }

        while (!dp[v].S.empty() && dp[v].a0 + sz(dp[v].S) > 1) {
            dp[v].S.erase(prev(dp[v].S.end()));
        }

        assert(sz(dp[v].S) >= 2);
        dp[v].h0 += edge_len[v];
        ll P = *dp[v].S.rbegin();
        dp[v].S.erase(prev(dp[v].S.end()));
        ll Q = *dp[v].S.rbegin();
        dp[v].S.erase(prev(dp[v].S.end()));
        dp[v].S.insert(P + edge_len[v]);
        dp[v].S.insert(Q + edge_len[v]);
    }

    ll val = dp[1].h0, slope = dp[1].a0;
    ll pos = 0;

    for (ll pt : dp[1].S) {
        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