Submission #684403

#	Time	Username	Problem	Language	Result	Execution time	Memory
684403		PoonYaPat	Fireworks (APIO16_fireworks)	C++14	26 / 100	16 ms	26580 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];
priority_queue<ll> lsq[300001];

void dfs(int x) {
    int cnt=0;
    priority_queue<ll, vector<ll>, greater<ll>> temp;

    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]);

        if (lsq[x].size()) {
            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]+=w[x];
    r[x]+=w[x];
    lsq[x].pop(); lsq[x].push(l[x]);
    rsq[x].push(r[x]);
}

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:50: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]
   50 |         while (temp.size()>cnt) lsq[x].push(temp.top()), temp.pop();
      |                ~~~~~~~~~~~^~~~
fireworks.cpp:51: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]
   51 |         while (temp.size()<cnt) temp.push(lsq[x].top()), lsq[x].pop();
      |                ~~~~~~~~~~~^~~~

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