Submission #49955

#	Time	Username	Problem	Language	Result	Execution time	Memory
49955		fallingstar	Fireworks (APIO16_fireworks)	C++17	100 / 100	556 ms	130320 KiB

fireworks

#include <iostream>
#include <vector>
#include <queue>

#define long long long

using namespace std;

const int N = 3e5 + 2;

int n, m;
vector<pair<int, int> > g[N];
priority_queue<long> q[N];
pair<int, long> line[N];

void Merge(priority_queue<long> &a, priority_queue<long> &b)
{
    if (a.size() < b.size()) a.swap(b);
    while (!b.empty()) a.push(b.top()), b.pop();
}

void Dfs(int u, int cost)
{
    if (u > n)
    {
        q[u].push(cost);
        q[u].push(cost);
        line[u] = make_pair(1, -cost);
        return;
    }
    for (auto e: g[u])
    {
        int v = e.first, c = e.second;
        Dfs(v, c);
        line[u].first += line[v].first;
        line[u].second += line[v].second;
        Merge(q[u], q[v]);
    }
    while (line[u].first > 1)
    {
        line[u].second += q[u].top();
        q[u].pop();
        --line[u].first;
    }
    long p1 = q[u].top(); q[u].pop();
    long p0 = q[u].top(); q[u].pop();
    q[u].push(p1 + cost);
    q[u].push(p0 + cost);
    line[u].second -= cost;
}

int main()
{
    cin >> n >> m;
    for (int i = 2; i <= n + m; ++i)
    {
        int p, c; cin >> p >> c;
        g[p].push_back(make_pair(i, c));
    }
    Dfs(1, 0);
    cout << line[1].second + q[1].top();
    return 0;
}

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