Submission #589195

#	Time	Username	Problem	Language	Result	Execution time	Memory
589195		jy0n	Fireworks (APIO16_fireworks)	C++17	100 / 100	397 ms	104964 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int __=3e5+1;
int n, m, par[__];
ll d[__], ans;
priority_queue<ll> a[__];
priority_queue<ll, vector<ll>, greater<ll>> b[__];
vector<pair<int,ll>> g[__];

int find(int u) {
    if (par[u]==u) return u;
    return par[u]=find(par[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u==v) return;
    if (a[u].size()>a[v].size()) swap(u, v);
    ll o = d[u]-d[v];
    while (a[u].size()) {
        ll x = a[u].top();
        a[u].pop();
        a[v].push(x+o);
    }
    par[u] = v;
}

void add(int u, ll r) {
    int uu = u;
    u = find(u);
    ll x = d[u]+a[u].top();
    if (r<x) {
        a[u].push(r-d[u]);
        a[u].pop();
        b[uu].push(x);
        ans += x-r;
    } else {
        b[uu].push(r);
    }
}

ll dfs(int i, int p) {
    vector<pair<ll, int>> v;
    for (auto [j, x]: g[i])
        if (j!=p) v.emplace_back(dfs(j, i), j);
    sort(v.begin(), v.end(), greater<pair<ll, int>>());
    for (auto [r, j]: v) {
        if (par[i]==i) {
            par[i] = j;
            b[i].push(r);
        } else {
            add(i, r);
            merge(i, j);
        }
    }
    int pi = find(i);
    ll r = b[i].size()? b[i].top() + d[i] : d[i];
    ll l = a[pi].size()? a[pi].top() + d[pi] + d[i] : d[i];
    if (a[pi].size()) a[pi].pop();
    a[pi].push(l-d[pi]);
    return r;
}

void init(int i, int p) {
    for (auto [j, c]: g[i])
        if (j!=p) {
            d[j] = c;
            init(j, i);
        }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n+m; ++i) par[i] = i;
    for (int i=2; i<=n+m; ++i) {
        int p; ll c;
        scanf("%d%lld", &p, &c);
        g[i].emplace_back(p, c);
        g[p].emplace_back(i, c);
    }
    init(1, 0);
    dfs(1, 0);
    printf("%lld\n", ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d%lld", &p, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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