Submission #1125542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125542		PVSekhar	Fireworks (APIO16_fireworks)	C++20	100 / 100	223 ms	94332 KiB

fireworks

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 3e5 + 2;

vector<vector<pair<int, int>>> edges(N);
vector<ll> dist(N, 0), ind(N), del(N, 0), a(N, 0), b(N, 0);
ll n, m;
vector<priority_queue<ll>> pq(N);

void merge(ll &node, ll child) {
    int n1 = pq[node].size();
    int n2 = pq[child].size();
    if (!n1) {
        node = child;
        return;
    }
    if (n1 < n2) swap(node, child);
    while (pq[child].size()) {
        pq[node].push(pq[child].top());
        pq[child].pop();
    }
}

void dfs(int node, int parent) {
    ll t1, t2, child = node, d;
    for (auto it : edges[node]) {
        child = it.first; d = it.second;
        if (child == parent) continue;
        if (n + 1 <= child && child <= n + m) {
            pq[child].push(d); pq[child].push(d);
            a[child] = 1;
            b[child] = -d;
        } else {
            dfs(child, node);
            b[child] -= d;
            t1 = pq[ind[child]].top();
            pq[ind[child]].pop();
            t2 = pq[ind[child]].top();
            pq[ind[child]].pop();
            t1 += d; t2 += d;
            pq[ind[child]].push(t2); pq[ind[child]].push(t1);
        }
        a[node] += a[child];
        b[node] += b[child];
        merge(ind[node], ind[child]);
    }
    while (a[node] > 1) {
        b[node] += pq[ind[node]].top();
        pq[ind[node]].pop();
        a[node]--;
    }
}

void solve() {
    ll p, c, ans = 0;
    cin >> n >> m;
    for (int i = 2; i <= n + m; i++) {
        cin >> p >> c;
        edges[p].push_back(make_pair(i, c));
        edges[i].push_back(make_pair(p, c));
    }
    for (int i = 1; i <= n + m; i++) ind[i] = i;
    dfs(1, 0);
    cout << a[1] * pq[ind[1]].top() + b[1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

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