Submission #982169

#	Time	Username	Problem	Language	Result	Execution time	Memory
982169		12345678	Fireworks (APIO16_fireworks)	C++17	100 / 100	185 ms	94520 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

const int nx=6e5+5;

#define ll long long

ll n, m, p, x, res;
vector<pair<ll, ll>> d[nx];
priority_queue<ll> pq[nx];

void dfs(int u)
{
    for (auto [v, w]:d[u])
    {
        dfs(v);
        res+=w;
        ll a=pq[v].top();
        pq[v].pop();
        ll b=pq[v].top();
        pq[v].pop();
        pq[v].push(a+w);
        pq[v].push(b+w);
        if (pq[v].size()>pq[u].size()) swap(pq[u], pq[v]);
        while (!pq[v].empty()) pq[u].push(pq[v].top()), pq[v].pop();
    }
    for (int i=1; i<d[u].size(); i++) pq[u].pop();
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=2; i<=n+m; i++) cin>>p>>x, d[p].push_back({i, x});
    for (int i=n+1; i<=n+m; i++) pq[i].push(0), pq[i].push(0);
    dfs(1);
    pq[1].pop();
    while (!pq[1].empty()) res-=pq[1].top(), pq[1].pop();
    cout<<res;
}

Compilation message (stderr)

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

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