Submission #684428

#	Time	Username	Problem	Language	Result	Execution time	Memory
684428		PoonYaPat	Fireworks (APIO16_fireworks)	C++14	7 / 100	14 ms	26196 KiB

fireworks

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

int n,m;
ll l[300001],r[300001],w[300001],Ymin[300001];
vector<int> adj[300001];
priority_queue<ll, vector<ll>, greater<ll>> rsq[300001],temp;
priority_queue<ll> lsq[300001];

void dfs(int x) {
    int cnt=0;

    if (!adj[x].size()) {

        l[x]=w[x]; r[x]=w[x];
        Ymin[x]=0;
        lsq[x].push(l[x]);
        rsq[x].push(r[x]);
        return;
    }

    for (auto s : adj[x]) {
        ++cnt;
        dfs(s);

        Ymin[x]+=Ymin[s];

        if (lsq[x].size()) {
            if (l[s]>r[x]) Ymin[x]+=l[s]-r[x];
            if (r[s]<l[x]) Ymin[x]+=l[x]-r[s];
        }

        if (lsq[s].size()+rsq[s].size()>lsq[x].size()+temp.size()) swap(lsq[x],lsq[s]), swap(temp,rsq[s]);

        while (!lsq[s].empty()) {
            if (lsq[s].top()>=temp.top()) temp.push(lsq[s].top());
            else lsq[x].push(lsq[s].top());
            lsq[s].pop();
        }

        while (!rsq[s].empty()) {
            if (rsq[s].top()>=temp.top()) temp.push(rsq[s].top());
            else lsq[x].push(rsq[s].top());
            rsq[s].pop();
        }

        while (temp.size()>cnt) lsq[x].push(temp.top()), temp.pop();
        while (temp.size()<cnt) temp.push(lsq[x].top()), lsq[x].pop();

        l[x]=lsq[x].top();
        r[x]=temp.top();

    }

    l[x]=lsq[x].top()+w[x];
    r[x]=temp.top()+w[x];
    lsq[x].pop(); lsq[x].push(l[x]);
    rsq[x].push(r[x]);

    while (temp.size()) temp.pop();
}

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);
    }
    dfs(1);
    cout<<Ymin[1];
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:48:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         while (temp.size()>cnt) lsq[x].push(temp.top()), temp.pop();
      |                ~~~~~~~~~~~^~~~
fireworks.cpp:49:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         while (temp.size()<cnt) temp.push(lsq[x].top()), lsq[x].pop();
      |                ~~~~~~~~~~~^~~~

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