Submission #708261

#	Time	Username	Problem	Language	Result	Execution time	Memory
708261		four_specks	Fireworks (APIO16_fireworks)	C++17	100 / 100	217 ms	89724 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

} // namespace

void solve()
{
    int n, m;
    cin >> n >> m;

    int k = n + m;

    vector<long> a(k);
    vector<vector<int>> adj(k);
    for (int u = 1; u < k; u++)
    {
        int p;
        cin >> p >> a[u], --p;

        adj[p].push_back(u);
    }

    long res = get<0>(YCombinator(
        [&](auto self, int u) -> tuple<long, priority_queue<long>, priority_queue<long, vector<long>, greater<long>>>
        {
            tuple<long, priority_queue<long>, priority_queue<long, vector<long>, greater<long>>> cost;
            auto &[val, lft, rgt] = cost;

            if (adj[u].empty())
            {
                lft.push(0);
                rgt.push(0);
            }

            for (int v : adj[u])
            {
                tuple cost_v = self(v);
                auto &[val_v, lft_v, rgt_v] = cost_v;

                if ((int)lft.size() + (int)rgt.size() < (int)lft_v.size() + (int)rgt_v.size())
                    swap(cost, cost_v);

                val += val_v;

                while (!lft_v.empty())
                {
                    long x = lft_v.top();
                    lft_v.pop();

                    rgt.push(x);
                    val += x - rgt.top();
                    lft.push(rgt.top());
                    rgt.pop();
                }

                while (!rgt_v.empty())
                {
                    long x = rgt_v.top();
                    rgt_v.pop();

                    lft.push(x);
                    val += lft.top() - x;
                    rgt.push(lft.top());
                    lft.pop();
                }
            }

            {
                long x = lft.top() + a[u];
                lft.pop();
                lft.push(x);
            }

            {
                long x = rgt.top() + a[u];
                while (!rgt.empty())
                    rgt.pop();
                rgt.push(x);
            }

            return cost;
        })(0));

    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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