Submission #778875

#	Time	Username	Problem	Language	Result	Execution time	Memory
778875		danikoynov	Fireworks (APIO16_fireworks)	C++14	19 / 100	54 ms	86096 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];
const int maxlen = 610;
ll dp[310][maxlen];
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;
        for (int j = 0; j < maxlen; j ++)
            dp[v][j] += dp[u][j];
        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();
        for (int j = 1; j < maxlen; j ++)
        {
            dp[v][j] = min(dp[v][j], dp[v][j - 1] + 1);
        }
    }
    else
    {
        fun[v].add_up_slope(0);
        for (int j = 0; j < maxlen; j ++)
            dp[v][j] = j;
    }
    //cout << "vertex " << v << " " << "fine" << endl;
    fun[v].shift_function(len);
    fun[v].shift_left_slope(len);
    for (int j = maxlen - 1; j >= len; j --)
    {
        dp[v][j] = dp[v][j - len];
    }
    for (int j = len - 1; j >= 0; j --)
    {
        dp[v][j] = inf;

    }
    ///int pt = 0;
    ///while(dp[v][pt] > dp[v][pt + 1])
       /// pt ++;
    for (int j = 0; j < maxlen; j ++)
    {
        for (int p = 1; p <= len; p ++)
        {
            if (j + p < maxlen)
                dp[v][j] = min(dp[v][j], dp[v][j + p] + p);
        }
    }
    /**cout << "---------------------" << endl;
    cout << "vertex " << v << endl;
    fun[v].print_function();

    for (int j = 0; j < 20; j ++)
        cout << dp[v][j] << " ";
    cout << endl;*/

}
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);
    ll ans = inf;
    for (int j = 0; j < maxlen; j ++)
        ans = min(ans, dp[1][j]);
    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: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45