Submission #470356

#	Time	Username	Problem	Language	Result	Execution time	Memory
470356		ymm	Fireworks (APIO16_fireworks)	C++17	100 / 100	265 ms	73364 KiB

fireworks

///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int N = 300'010;
vector<pll> A[N];
int n, m;

struct obj
{
    priority_queue<ll, vector<ll>, less<ll>   > l;
    priority_queue<ll, vector<ll>, greater<ll>> r;
    ll w=0;

    void add(ll x)
    {
        if(!l.size()) l.push(0);
        if(!r.size()) r.push(1e15);
        ll nl = l.top()+x;
        ll nr = r.top()+x;
        l.pop(); l.push(nl);
        while(r.size()) r.pop(); r.push(nr);
    }

    void add(obj& x)
    {
        w += x.w;
        if(l.size() < x.l.size()) l.swap(x.l);
        if(r.size() < x.r.size()) r.swap(x.r);
        while(x.l.size()) l.push(x.l.top()), x.l.pop();
        while(x.r.size()) r.push(x.r.top()), x.r.pop();
        while(l.size() && r.size() && l.top() > r.top())
        {
            auto _l = l.top(), _r = r.top();
            l.pop(); r.pop();
            l.push(_r); r.push(_l);
            w += _l - _r;
        }
    }
};

obj* dfs(int v)
{
    obj* ans = new obj;
    if(v >= n) {ans->r.push(0); return ans;}
    for(auto [u, w] : A[v])
    {
        auto x = dfs(u);
        x->add(w);
        ans->add(*x);
    }
    return ans;
}

int main()
{
    FAST;
    cin >> n >> m;
    Loop(i,1,n+m)
    {
        ll v, c;
        cin >> v >> c;
        --v;
        A[v].emplace_back(i,c);
    }
    cout << dfs(0)->w;
}

Compilation message (stderr)

fireworks.cpp: In member function 'void obj::add(ll)':
fireworks.cpp:38:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   38 |         while(r.size()) r.pop(); r.push(nr);
      |         ^~~~~
fireworks.cpp:38:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   38 |         while(r.size()) r.pop(); r.push(nr);
      |                                  ^

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