Submission #778854

#	Time	Username	Problem	Language	Result	Execution time	Memory
778854		danikoynov	Fireworks (APIO16_fireworks)	C++14	19 / 100	51 ms	86024 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() + right_offset;
    }

    ll get_right()
    {
        if (right_set.empty())
            return inf;
        return *right_set.begin() + left_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));
            left_set.insert(right - left_offset);
            height = height  + (value - right);
        }
    }

    void add_up_slope(ll value)
    {
        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));
            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;
    }
};

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);
        ///fun[u].shift_function(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 (int j = 0; j < maxlen; j ++)
            dp[v][j] += dp[u][j];
        /**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[v].height);*/
    }
    if (sub[v] > 1)
    {

        for (int j = 1; j < maxlen; j ++)
        {
            dp[v][j] = min(dp[v][j], dp[v][j - 1] + 1);
        }
    }
    else
    {
        for (int j = 0; j < maxlen; j ++)
            dp[v][j] = j;
    }
    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;

    }
    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 << v << endl;
    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 << ans << endl;

}

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

Compilation message (stderr)

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

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