Submission #175350

#	Time	Username	Problem	Language	Result	Execution time	Memory
175350		onjo0127	Fireworks (APIO16_fireworks)	C++11	100 / 100	428 ms	86452 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pil = pair<int, ll>;

ll zv[300009];
priority_queue<ll> pq[300009];
vector<pil> T[300009];
int sz[300009];

void dfs(int x) {
    sz[x] = 1;
    for(auto& it: T[x]) {
        dfs(it.first);
        sz[x] += sz[it.first];
    }
    sort(T[x].begin(), T[x].end(), [&](pil P, pil Q) { return sz[P.first] > sz[Q.first]; });
}

void go(int x, int p, ll pc) {
    if(T[x].empty()) return;
    int mxi = T[x][0].first;
    for(auto& it: T[x]) go(it.first, p, it.second);
    for(auto& it: T[x]) {
        if(it.first == mxi) continue;
        int t; ll c; tie(t, c) = it;
        while(pq[t].size()) {
            pq[mxi].push(pq[t].top());
            pq[t].pop();
        }
        zv[mxi] += zv[t];
    }
    vector<ll> S;
    for(int i=0; i<(int)T[x].size()-1; i++) {
        S.push_back(pq[mxi].top());
        pq[mxi].pop();
    }
    ll a = pq[mxi].top() + pc; pq[mxi].pop();
    ll b = pq[mxi].top() + pc; pq[mxi].pop();
    pq[mxi].push(a); pq[mxi].push(b);
    swap(pq[mxi], pq[x]);
    zv[x] = zv[mxi] + pc;
}

int main() {
    int N, M; scanf("%d%d",&N,&M);
    for(int i=2; i<=N+M; i++) {
        int p, c; scanf("%d%d",&p,&c);
        T[p].push_back({i, c});
        if(i > N) {
            pq[i].push(c);
            pq[i].push(c);
            zv[i] = c;
        }
    }
    dfs(1);
    go(1, 1, 0);
    vector<ll> S;
    while(pq[1].size()) {
        S.push_back(pq[1].top());
        pq[1].pop();
    }
    reverse(S.begin(), S.end());
    ll ans = zv[1], pr = 0, inc = (int)S.size() - 1;
    for(auto& it: S) {
        ans -= (it - pr) * inc;
        pr = it;
        --inc;
    }
    printf("%lld", ans);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:46:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d%d",&N,&M);
               ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int p, c; scanf("%d%d",&p,&c);
                   ~~~~~^~~~~~~~~~~~~~

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