#pragma GCC omptimize("unroll-loops")
#pragma optimize("SEX_ON_THE_BEACH")
#pragma GCC optimize("no-stack-protector")
#pragma comment(linker, "/STACK:1000000000")
#include<bits/stdc++.h>
using namespace std;
//#define need_tree
#ifdef need_tree
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif // need_tree
using ll = unsigned long long int;
using ull = unsigned long long int;
using dd = long double;
using ldd = long double;
using si = short int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
ll get_seed(string s)
{
ll ans = 0;
for (int i = 0; i < s.size(); ++i)
ans += s[i];
return ans;
}
int popcount(int x)
{
return __builtin_popcount(x);
}
ll popcountll(ll x)
{
return __builtin_popcount(x);
}
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
// debug defines
#ifdef HOME
int jjj;
#define PO cout << "Pomelo" << endl;
#define OL cout << "Oliva" << endl;
#define debug(x) cout << #x << " " << x << endl;
#define debug_p(x) cout << #x << " " << x.ff << " " << x.ss << endl;
#define debug_v(x) cout << #x << " "; for (auto iii : x) cout << iii << " "; cout << endl;
#define debug_vp(x) cout << #x << " "; for (auto ii : x) cout << '[' << ii.ff << " " << ii.ss << ']'; cout << endl;
#define wait() cin >> jjj;
#else
#define PO 0;
#define OL 0;
#define debug(x) 0;
#define debug_p(x) 0;
#define debug_vp(x) 0;
#define debug_v(x) 0;
#define debug_vp(x) 0;
#define wait() 0;
#endif // HOME
// end of debug defines
ll normilize(vector<pair<ll, ll>>& arr)
{
if (arr.size() == 1)
return 0;
vector<pair<ll, int>> tp;
for (int i = 0; i < arr.size(); ++i)
{
tp.push_back({arr[i].ff, 1});
tp.push_back({arr[i].ss, -1});
}
sort(all(tp));
int n = arr.size();
int nw = 0;
for (int i = 0; i < tp.size(); ++i)
{
if (tp[i].ss == 1)
{
n--;
}
else
{
nw++;
}
if (nw >= n)
{
ll tmp = 0;
ll x = tp[i].ff;
debug(x);
for (int i = 0; i < arr.size(); ++i)
{
if (arr[i].ff > x)
{
tmp += arr[i].ff - x;
}
else if (arr[i].ss < x)
{
tmp += x - arr[i].ss;
}
}
arr.clear();
arr.push_back({tp[i].ff, tp[i + 1].ff});
return tmp;
}
}
}
void solve(int i)
{
int n, m;
cin >> n >> m;
vector<int> pre(n + m);
vector<ll> cost(n + m);
vector<ll> dp(n + m);
vector<vector<pair<ll, ll>>> can(n + m);
pre[0] = -1;
for (int i = 1; i < n; ++i)
{
cin >> pre[i] >> cost[i];
--pre[i];
}
for (int i = 0; i < m; ++i)
{
cin >> pre[i + n] >> cost[i + n];
--pre[i + n];
dp[i + n] = 0;
can[pre[i + n]].push_back({cost[i + n], cost[i + n]});
}
for (int i = n - 1; i > 0; --i)
{
debug(i + 1);
debug_vp(can[i]);
debug(dp[i]);
dp[i] += normilize(can[i]);
debug(dp[i]);
debug_vp(can[i]);
debug(cost[i]);
can[pre[i]].push_back({can[i][0].ff + cost[i], can[i][0].ss + cost[i]});
dp[pre[i]] += dp[i];
}
dp[0] += normilize(can[0]);
cout << dp[0];
}
int main()
{
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t;
t = 1;
//cin >> t;
for (int i = 0; i < t; ++i)
solve(i);
return 0;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/
Compilation message
fireworks.cpp:1:0: warning: ignoring #pragma GCC omptimize [-Wunknown-pragmas]
#pragma GCC omptimize("unroll-loops")
fireworks.cpp:2:0: warning: ignoring #pragma optimize [-Wunknown-pragmas]
#pragma optimize("SEX_ON_THE_BEACH")
fireworks.cpp:4:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK:1000000000")
fireworks.cpp: In function 'll get_seed(std::__cxx11::string)':
fireworks.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); ++i)
~~^~~~~~~~~~
fireworks.cpp: In function 'll normilize(std::vector<std::pair<long long unsigned int, long long unsigned int> >&)':
fireworks.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); ++i)
~~^~~~~~~~~~~~
fireworks.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tp.size(); ++i)
~~^~~~~~~~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
#define debug(x) 0;
^
fireworks.cpp:97:13: note: in expansion of macro 'debug'
debug(x);
^~~~~
fireworks.cpp:98:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); ++i)
~~^~~~~~~~~~~~
fireworks.cpp: In function 'void solve(int)':
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
#define debug(x) 0;
^
fireworks.cpp:140:9: note: in expansion of macro 'debug'
debug(i + 1);
^~~~~
fireworks.cpp:65:26: warning: statement has no effect [-Wunused-value]
#define debug_vp(x) 0;
^
fireworks.cpp:141:9: note: in expansion of macro 'debug_vp'
debug_vp(can[i]);
^~~~~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
#define debug(x) 0;
^
fireworks.cpp:142:9: note: in expansion of macro 'debug'
debug(dp[i]);
^~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
#define debug(x) 0;
^
fireworks.cpp:144:9: note: in expansion of macro 'debug'
debug(dp[i]);
^~~~~
fireworks.cpp:65:26: warning: statement has no effect [-Wunused-value]
#define debug_vp(x) 0;
^
fireworks.cpp:145:9: note: in expansion of macro 'debug_vp'
debug_vp(can[i]);
^~~~~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
#define debug(x) 0;
^
fireworks.cpp:146:9: note: in expansion of macro 'debug'
debug(cost[i]);
^~~~~
fireworks.cpp: In function 'll normilize(std::vector<std::pair<long long unsigned int, long long unsigned int> >&)':
fireworks.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
