제출 #165575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165575		combi1k1	Fireworks (APIO16_fireworks)	C++14	55 / 100	934 ms	524292 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;

    Data 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();
        }
        return  *this;
    }
}   f[N];

vector<int> g[N];

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

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

    vector<int> c(n + m + 1);

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

    function<void(int)> dfs = [&](int u)    {
        if (u > n)  {
            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[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);
    };  dfs(1);

    cout << f[1].b + f[1].pq.top() << endl;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

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