Submission #1266427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266427		nhphuc	Fireworks (APIO16_fireworks)	C++20	100 / 100	186 ms	103424 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

const int N = 600300;

int n, m, in[N];
vector<int> adj[N];
priority_queue<long long> *pq[N];
long long dp[N];

void dfs (int u){
    int c = 0;
    pq[u] = new (priority_queue<long long>); 
    pq[u]-> push(0ll);
    pq[u]-> push(0ll);
    for (int v : adj[u]){
        dfs(v);
        ++c;
        dp[u] += dp[v];
        if (pq[u]-> size() < pq[v]-> size()){
            swap(pq[u], pq[v]);
        }
        while (pq[v]-> size()){
            pq[u]-> push(pq[v]-> top());
            pq[v]-> pop();
        }
    }
    while (c > 1){
        --c;
        dp[u] += pq[u]-> top();
        pq[u]-> pop();
    }
    long long l = pq[u]-> top(); pq[u]-> pop();
    long long r = pq[u]-> top(); pq[u]-> pop();
    pq[u]-> push(l + in[u]);
    pq[u]-> push(r + in[u]);
    dp[u] -= 1ll * in[u];
    return;
}

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    const string task = "test";
    if (fopen ((task + ".inp").c_str(), "r")){
        freopen ((task + ".inp").c_str(), "r", stdin);
        freopen ((task + ".out").c_str(), "w", stdout);
    }
    cin >> n >> m;
    for (int i = 2; i <= n + m; ++i){
        int p; cin >> p >> in[i];
        adj[p].push_back(i);
    }
    dfs(1);
    cout << pq[1]-> top() + dp[1] << "\n";
}

Compilation message (stderr)

fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:45:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen ((task + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:46:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen ((task + ".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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