제출 #415525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415525		Aldas25	Fireworks (APIO16_fireworks)	C++14	26 / 100	14 ms	16844 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 300100, MAXK = 30;
//const ll MOD = 998244353;
const ll INF = 4e18;
const ld PI = asin(1) * 2;

priority_queue<ll> q[MAXN];
int p[MAXN];
ll c[MAXN];
vi adj[MAXN];
int n, m;
int bg[MAXN];

void print (int i) {
    cout << " queue i=" << i << ": ";
    priority_queue<ll> tmp;
    while (!q[i].empty()) {
        ll x = q[i].top();
        q[i].pop();
        tmp.push(x);
        cout << " " << x;
    }
    while (!tmp.empty()) {
        ll x = tmp.top();
        tmp.pop();
        q[i].push(x);
        //cout << " " << x;
    }
    cout << endl;
}

void dfs (int v) {
   // cout << " v = " << v << endl;
    bg[v] = v;
    if (n+1 <= v) {
        REP(2) q[v].push(c[v]);
        //print(v);
        return;
    }
    for (int u : adj[v]) {
        dfs(u);

        if ((int)q[bg[u]].size() > (int)q[bg[v]].size()) bg[v] = bg[u];

        /*if ((int)q[u].size() > (int)q[v].size()) swap(q[u], q[v]);
        while (!q[u].empty()) {
            q[v].push(q[u].top());
            q[u].pop();
        }*/
    }
    for (int u : adj[v]) {
        //dfs(u);

        //if ((int)q[bg[u]].size() > (int)q[bg[v]].size()) bg[v] = bg[u];

        //if ((int)q[u].size() > (int)q[v].size()) swap(q[u], q[v]);
        if (bg[u] == bg[v]) continue;
        while (!q[bg[u]].empty()) {
            q[bg[v]].push(q[bg[u]].top());
            q[bg[u]].pop();
        }
    }



    int sz = (int)adj[v].size();
    REP(sz-1) q[bg[v]].pop();
    int fr, to;
    to = q[bg[v]].top();
    q[bg[v]].pop();
    fr = q[bg[v]].top();
    q[bg[v]].pop();
    q[bg[v]].push(fr+c[v]);
    q[bg[v]].push(to+c[v]);


   // print(v);
}

int main()
{
    FAST_IO;

    cin >> n >> m;
    FOR(i, 2, n+m) {
        cin >> p[i] >> c[i];
        adj[p[i]].pb(i);
    }

    /*FOR(i, 1, n+m) {
        cout << "    i = " << i << "  adj: ";
        for (int x : adj[i]) cout << x << " ";
        cout << endl;
    }*/

    dfs (1);

    ll cur = 0;
    FOR(i, 1, n+m) cur += c[i];

    q[bg[1]].pop();
    while (!q[bg[1]].empty()) {
        cur -= q[bg[1]].top();
        q[bg[1]].pop();
    }

    cout << cur << "\n";


    return 0;
}

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