Submission #580503

#	Time	Username	Problem	Language	Result	Execution time	Memory
580503		islingr	Fireworks (APIO16_fireworks)	C++17	100 / 100	186 ms	43764 KiB

fireworks

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ld = long double;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a);)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) static_cast<int>((x).size())

template <class T>
bool uin(T& a, const T& b) {
    return a > b ? a = b, true : false;
}
template <class T>
bool uax(T& a, const T& b) {
    return a < b ? a = b, true : false;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    swap(n, m);
    n += m;

    vector<int> p(n), c(n);
    rep(i, 1, n) {
        cin >> p[i] >> c[i];
        --p[i];
    }

    struct node {
        int a;
        ll b;
        priority_queue<ll> q;
        node() : a{0}, b{0} {}
        node(int x) : a{1}, b{-x}, q(2, x) {}
        void merge(node& o) {
            a += o.a;
            b += o.b;
            if (sz(q) < sz(o.q)) swap(q, o.q);
            while (!o.q.empty()) {
                q.push(o.q.top());
                o.q.pop();
            }
        }
    };

    vector<node> data(n);
    per(i, m, n) {
        data[i] = node(c[i]);
        data[p[i]].merge(data[i]);
    }

    per(i, 1, m) {
        const auto x = c[i];
        auto& [a, b, q] = data[i];
        while (a > 1) {
            --a;
            b += q.top();
            q.pop();
        }
        const auto one = q.top();
        q.pop();
        const auto zero = q.top();
        q.pop();
        q.push(one + x);
        q.push(zero + x);
        b -= x;
        data[p[i]].merge(data[i]);
    }

    auto& [a, b, q] = data[0];
    while (a > 0) {
        --a;
        b += q.top();
        q.pop();
    }
    cout << b << '\n';
}

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