oj.uz

Submission #778854

# Submission time Handle Problem Language Result Execution time Memory
778854 2023-07-10T20:55:42 Z danikoynov Fireworks (APIO16_fireworks) C++14
19 / 100
 51 ms 86024 KB 
/**
 ____ ____ ____ ____ ____ ____
||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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 86024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 21 ms 42756 KB Output is correct
3 Correct 21 ms 42824 KB Output is correct
4 Correct 19 ms 42964 KB Output is correct
5 Correct 25 ms 43092 KB Output is correct
6 Correct 25 ms 43220 KB Output is correct
7 Correct 20 ms 43332 KB Output is correct
8 Correct 23 ms 43440 KB Output is correct
9 Correct 23 ms 43432 KB Output is correct
10 Correct 23 ms 43604 KB Output is correct
11 Correct 24 ms 43604 KB Output is correct
12 Correct 24 ms 43816 KB Output is correct
13 Correct 25 ms 43848 KB Output is correct
14 Correct 20 ms 43992 KB Output is correct
15 Correct 26 ms 44024 KB Output is correct
16 Correct 25 ms 43984 KB Output is correct
17 Correct 26 ms 43976 KB Output is correct
18 Correct 24 ms 43932 KB Output is correct
19 Correct 25 ms 43988 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 86024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 86024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -