Submission #1085156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085156		ZeroCool	Fireworks (APIO16_fireworks)	C++14	100 / 100	166 ms	71052 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define ar array

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int N = 3e5 + 20;



priority_queue<int> pq[N];
int n, m, A[N];
vector<int> g[N];

void dfs(int x){
    for(auto u: g[x]){
        dfs(u);
        if(pq[u].size() > pq[x].size())swap(pq[u], pq[x]);
        while(pq[u].size()){
            pq[x].push(pq[u].top());
            pq[u].pop();
        }
    }
    int l = 0, r = 0;
    if(x < n){
        for(int i = 1;i < g[x].size();i++)pq[x].pop();
        l = pq[x].top();
        pq[x].pop();
        r = pq[x].top();
        pq[x].pop();
    }
    pq[x].push(l + A[x]);
    pq[x].push(r + A[x]);
}

signed main() {ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    int ans = 0;
    for(int i = 1;i < n + m;i++){
        int p;
        cin>>p>>A[i];
        --p;   
        g[p].push_back(i);
        ans += A[i];
    }
    dfs(0);
    pq[0].pop();
    while(pq[0].size()){
        ans -= pq[0].top();
        pq[0].pop();
    }
    cout<<ans;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(long long int)':
fireworks.cpp:29:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i = 1;i < g[x].size();i++)pq[x].pop();
      |                       ~~^~~~~~~~~~~~~

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