Submission #165579

#	Time	Username	Problem	Language	Result	Execution time	Memory
165579		combi1k1	Fireworks (APIO16_fireworks)	C++14	100 / 100	363 ms	66168 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   N   = 3e5 + 1;

struct Data {
    int a, b;
    priority_queue<int> pq;

    void operator += (Data &x)  {
        a += x.a;
        b += x.b;

        if (pq.size() < x.pq.size())
            pq.swap(x.pq);

        while (x.pq.size()) {
            pq.push(x.pq.top());
            x.pq.pop();
        }
    }
}   f[N];
int c[N];

vector<int> g[N];

void dfs(int u) {
    if (g[u].empty())   {
        f[u].a = 1;
        f[u].b = -c[u];
        f[u].pq.push(c[u]);
        f[u].pq.push(c[u]);
        return;
    }
    for(int v : g[u])
        dfs(v), f[u] += f[v];

    for(; f[u].a > 1 ;)
        f[u].a--,
        f[u].b += f[u].pq.top(),
        f[u].pq.pop();

    int x = f[u].pq.top() + c[u];   f[u].pq.pop();
    int y = f[u].pq.top() + c[u];   f[u].pq.pop();

    f[u].b -= c[u];

    f[u].pq.push(x);
    f[u].pq.push(y);
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;

    for(int i = 2 ; i <= n + m ; ++i)   {
        int p;
        cin >> p;
        cin >> c[i];
        g[p].push_back(i);
    }

    dfs(1); cout << f[1].b + f[1].pq.top() << endl;
}

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