Submission #952920

#	Time	Username	Problem	Language	Result	Execution time	Memory
952920		ttamx	Fireworks (APIO16_fireworks)	C++17	100 / 100	225 ms	99156 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=6e5+5;

int n,m;
vector<pair<int,int>> adj[N];
priority_queue<ll> dp[N];
ll ans;

void dfs(int u){
    for(auto [v,w]:adj[u]){
        dfs(v);
        ll x=dp[v].top();
        dp[v].pop();
        ll y=dp[v].top();
        dp[v].pop();
        dp[v].emplace(x+w),dp[v].emplace(y+w);
        if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]);
        while(!dp[v].empty()){
            dp[u].emplace(dp[v].top());
            dp[v].pop();
        }
    }
    for(int i=1;i<adj[u].size();i++)dp[u].pop();
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=2;i<=n+m;i++){
        int p,c;
        cin >> p >> c;
        adj[p].emplace_back(i,c);
        ans+=c;
    }
    for(int i=1;i<=m;i++){
        dp[n+i].emplace(0);
        dp[n+i].emplace(0);
    }
    dfs(1);
    dp[1].pop();
    while(!dp[1].empty()){
        ans-=dp[1].top();
        dp[1].pop();
    }
    cout << ans;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=1;i<adj[u].size();i++)dp[u].pop();
      |                 ~^~~~~~~~~~~~~~

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