Submission #684434

#	Time	Username	Problem	Language	Result	Execution time	Memory
684434		PoonYaPat	Fireworks (APIO16_fireworks)	C++14	100 / 100	218 ms	75636 KiB

fireworks

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

int n,m;
ll w[300001],ans;
vector<int> adj[300001];
priority_queue<ll> q[300001];

void dfs(int x) {

    if (adj[x].size()==0) {
        q[x].push(w[x]);
        q[x].push(w[x]);
        return;
    }

    for (auto s : adj[x]) {
        dfs(s);
        if (q[s].size()>q[x].size()) swap(q[s],q[x]);
        while (!q[s].empty()) q[x].push(q[s].top()), q[s].pop();
    }

    for (int i=1; i<adj[x].size(); ++i) q[x].pop();
    ll a=q[x].top()+w[x]; q[x].pop();
    ll b=q[x].top()+w[x]; q[x].pop();
    q[x].push(a); q[x].push(b);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=2; i<=n+m; ++i) {
        int u; cin>>u>>w[i];
        adj[u].push_back(i);
    }
    for (int i=1; i<=n+m; ++i) ans+=w[i];
    dfs(1);

    q[1].pop();
    while (!q[1].empty()) ans-=q[1].top(), q[1].pop();
    cout<<ans;
}

Compilation message (stderr)

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

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