Submission #373727

#	Time	Username	Problem	Language	Result	Execution time	Memory
373727		KoD	Fireworks (APIO16_fireworks)	C++17	100 / 100	500 ms	110300 KiB

fireworks

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;
using ll = long long;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);        
    }
};

struct SlopeTrick {
    ll last_slope, last_y;
    std::priority_queue<ll> changes;

    SlopeTrick(): last_slope(), last_y(), changes() { 
        changes.push(0);
    }
    
    void absorb(SlopeTrick &&other) {
        const auto x1 = changes.top();
        const auto x2 = other.changes.top();
        last_y += other.last_y + (x1 < x2 ? last_slope * (x2 - x1) : other.last_slope * (x1 - x2));
        last_slope += other.last_slope;
        if (changes.size() < other.changes.size()) {
            std::swap(changes, other.changes);
        }
        while (!other.changes.empty()) {
            changes.push(other.changes.top());
            other.changes.pop();
        }
    }

    bool pop_last() {
        const auto x1 = changes.top();
        changes.pop();
        if (changes.empty()) return false;
        const auto x2 = changes.top();
        last_slope -= 1;
        last_y += last_slope * (x2 - x1);
        return true;
    }
};

int main() {
    int N, M;
    std::cin >> N >> M;
    Vec<Vec<std::pair<int, int>>> children(N + M);
    for (int i = 1; i < N + M; ++i) {
        int p, c;
        std::cin >> p >> c;
        p -= 1;
        children[p].emplace_back(i, c);
    }
    Vec<SlopeTrick> data(N);
    RecLambda([&](auto dfs, const int u) -> void {
        for (const auto [v, c]: children[u]) {
            if (v >= N) {
                SlopeTrick trick;
                trick.last_slope = 1;
                trick.changes.push(c);
                trick.changes.push(c);
                data[u].absorb(std::move(trick));
            }
            else {
                dfs(v);
                while (data[v].last_slope > 1) {
                    data[v].pop_last();
                }
                const auto x1 = data[v].changes.top();
                data[v].changes.pop();
                const auto x2 = data[v].changes.top();
                data[v].changes.pop();
                data[v].changes.push(x2 + c);
                data[v].changes.push(x1 + c);
                data[u].absorb(std::move(data[v]));
            }
        }
    })(0);
    ll ans = data[0].last_y;
    while (data[0].pop_last()) {
        ans = std::min(ans, data[0].last_y);
    }
    std::cout << ans << '\n';
    return 0;    
}

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