/**
____ ____ ____ ____ ____ ____
||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
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)
| ~~~~~ ^~ ~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
86096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
42580 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42704 KB |
Output is correct |
| 3 |
Correct |
22 ms |
42800 KB |
Output is correct |
| 4 |
Correct |
20 ms |
42964 KB |
Output is correct |
| 5 |
Correct |
22 ms |
43092 KB |
Output is correct |
| 6 |
Correct |
22 ms |
43140 KB |
Output is correct |
| 7 |
Correct |
21 ms |
43328 KB |
Output is correct |
| 8 |
Correct |
23 ms |
43416 KB |
Output is correct |
| 9 |
Correct |
24 ms |
43476 KB |
Output is correct |
| 10 |
Correct |
24 ms |
43604 KB |
Output is correct |
| 11 |
Correct |
25 ms |
43676 KB |
Output is correct |
| 12 |
Correct |
25 ms |
43732 KB |
Output is correct |
| 13 |
Correct |
26 ms |
43828 KB |
Output is correct |
| 14 |
Correct |
21 ms |
43988 KB |
Output is correct |
| 15 |
Correct |
27 ms |
43988 KB |
Output is correct |
| 16 |
Correct |
25 ms |
43940 KB |
Output is correct |
| 17 |
Correct |
27 ms |
44020 KB |
Output is correct |
| 18 |
Correct |
28 ms |
44000 KB |
Output is correct |
| 19 |
Correct |
27 ms |
43980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
86096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
86096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
