Submission #778876

#	Time	Username	Problem	Language	Result	Execution time	Memory
778876		danikoynov	Fireworks (APIO16_fireworks)	C++14	100 / 100	437 ms	123056 KiB

fireworks

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;
const ll inf = 1e18;

struct slope_trick
{
    multiset < ll > left_set, right_set;
    ll left_offset, right_offset, height;

    slope_trick()
    {
        left_offset = right_offset = height = 0;
    }

    ll get_left()
    {
        if (left_set.empty())
            return - inf;
        return *left_set.rbegin() + left_offset;
    }

    ll get_right()
    {
        if (right_set.empty())
            return inf;
        return *right_set.begin() + right_offset;
    }

    void add_down_slope(ll value)
    {
        ll left = get_left();
        ll right = get_right();
        if (value >= left && value <= right)
        {
            left_set.insert(value - left_offset);
        }
        else if (value < left)
        {
            left_set.insert(value - left_offset);
        }
        else if (value > right)
        {

            right_set.erase(right_set.find(right - right_offset));
            right_set.insert(value - right_offset);
            left_set.insert(right - left_offset);
            height = height  + (value - right);
        }
    }

    void add_up_slope(ll value)
    {
        ///cout << "add up slope " << value << endl;
        ll left = get_left();
        ll right = get_right();

        if (value >= left && right <= right)
        {
            right_set.insert(value - right_offset);
        }
        else if (value < left)
        {
            left_set.erase(left_set.find(left - left_offset));
            left_set.insert(value - left_offset);
            right_set.insert(left - right_offset);
            height = height + (left - value);
        }
        else
        {
            right_set.insert(value - right_offset);
        }
    }

    void shift_height(ll value)
    {
        height += value;
    }

    void shift_function(ll value)
    {
        left_offset += value;
        right_offset += value;
    }

    void upperize()
    {
        assert(right_set.size() != 0);
        ll right = get_right();
        right_set.clear();
        right_set.insert(right - right_offset);
    }

    void shift_left_slope(ll value)
    {
        ///assert(left_set.size() != 0);
        if (left_set.size() == 0)
        {
            left_set.insert(value - left_offset);
            return;
        }
        ll left = get_left();
        left_offset -= value;
        left_set.erase(left_set.find(*left_set.rbegin()));
        left_set.insert(left - left_offset);
    }

    void print_function()
    {
        cout << "left slope:" << endl;
        for (ll v : left_set)
        cout << v + left_offset << " ";
        cout << endl;
        cout << "right slope:" << endl;
        for (ll v : right_set)
            cout << v + right_offset << " ";
        cout << endl;
        cout << "height: " << height << endl;
    }
};

int n, m, sub[maxn];
vector < pair < int, ll > > adj[maxn];
slope_trick fun[maxn];

void dfs(int v, ll len)
{
    int heavy = -1;

    sub[v] = 1;
    for (pair < int, ll > nb : adj[v])
    {
        int u = nb.first;
        ll w = nb.second;
        dfs(u, w);
        sub[v] += sub[u];
        if (heavy == -1 || sub[u] > sub[heavy])
            heavy = u;
    }

    if (heavy != -1)
      swap(fun[v], fun[heavy]);
    for (pair < int, ll > nb : adj[v])
    {
        int u = nb.first;

        if (u == heavy)
          continue;

        ///cout << "edge " << v << " " << u << endl;
        for (ll value : fun[u].left_set)
            fun[v].add_down_slope(value + fun[u].left_offset);

        for (ll value : fun[u].right_set)
            fun[v].add_up_slope(value + fun[u].right_offset);

        fun[v].shift_height(fun[u].height);
    }
    if (sub[v] > 1)
    {
        fun[v].upperize();

    }
    else
    {
        fun[v].add_up_slope(0);

    }
    //cout << "vertex " << v << " " << "fine" << endl;
    fun[v].shift_function(len);
    fun[v].shift_left_slope(len);



}
void solve()
{
    cin >> n >> m;
    for (int i = 2; i <= n + m; i ++)
    {
        int p;
        ll c;
        cin >> p >> c;
        adj[p].push_back({i, c});
    }

    dfs(1, 0);

    cout << fun[1].height << endl;

}

int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In member function 'void slope_trick::add_up_slope(ll)':
fireworks.cpp:77:36: warning: self-comparison always evaluates to true [-Wtautological-compare]
   77 |         if (value >= left && right <= right)
      |                              ~~~~~ ^~ ~~~~~

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