제출 #126996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126996		srvlt	Fireworks (APIO16_fireworks)	C++14	7 / 100	40 ms	35704 KiB

fireworks

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;

const int N = 3e5 + 3;
int n, m, d[N], fv[N], sv[N];
vector <pair <int, int> > q[N];
multiset <int> f[N], s[N];

void add(int v, int x) {
    if (!s[v].empty() && *s[v].begin() > x) {
        f[v].insert(x);
        fv[v] += x;
    }   else {
        s[v].insert(x);
        sv[v] += x;
    }
    if (f[v].size() > s[v].size()) {
        int tmp = *(--f[v].end());
        f[v].erase(--f[v].end());
        fv[v] -= tmp;
        s[v].insert(tmp);
        sv[v] += tmp;
    }
    if (s[v].size() > f[v].size() + 1) {
        int tmp = *s[v].begin();
        s[v].erase(s[v].begin());
        sv[v] -= tmp;
        f[v].insert(tmp);
        fv[v] += tmp;
    }
}

int get(int v) {
    int x = *s[v].begin();
    return (x * (int)f[v].size() - fv[v]) + (sv[v] - x * (int)s[v].size());
}

void dfs(int v, int p) {
    for (auto i : q[v]) {
        if (i.fi != p) {
            dfs(i.fi, v);
            d[v] += d[i.fi];
            add(v, d[i.fi] + i.se);
        }
    }
    if (q[v].size() > 2)
        d[v] += get(v);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i = 2; i <= n + m; i++) {
        int x, y;
        cin>>x>>y;
        q[x].pb({i, y});
        q[i].pb({x, y});
    }
    dfs(1, 1);
    cout<<d[1];
}

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