#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007
int N, M;
vector<pair<int, LL>> edge[300001];
int par[300001];
vector<pair<int, LL>> chi[300001];
vector<pair<int, int>> node;
LL a[300001] ={}, b[300001] ={};
void dfs(int now, int p){
for(int i=0; i<edge[now].size(); i++){
if(edge[now][i].first == p) continue;
chi[now].PB(MP(edge[now][i].first, edge[now][i].second));
par[edge[now][i].first] = now;
dfs(edge[now][i].first, now);
}
}
int d[300001] ={};
int depth(int now){
if(now == 0) return 0;
if(d[now] != 0) return d[now];
return d[now] = depth(par[now]) + 1;
}
LL my_binary_search(int now, LL ans, LL ok, LL ng){
while(abs(ok-ng) > 1){
LL m = (ok+ng) / 2;
LL tmp = 0;
for(int i=0; i<chi[now].size(); i++){
if(a[chi[now][i].first] > m) tmp += a[chi[now][i].first] - m;
else if(b[chi[now][i].first] < m) tmp += m - b[chi[now][i].first];
}
if(tmp == ans) ok = m;
else ng = m;
}
return ok;
}
LL func(int now, LL tmp){
LL ans = 0;
for(int i=0; i<chi[now].size(); i++){
if(a[chi[now][i].first] > tmp) ans += a[chi[now][i].first] - tmp;
else if(b[chi[now][i].first] < tmp) ans += tmp - b[chi[now][i].first];
}
return ans;
}
LL sanbun(int now){
LL l = 0;
LL r = 1000000000LL*300000LL;
//[l,r)
while(r-l > 1){
LL m = (l+r) / 2;
if(func(now, m-1) <= func(now, m)) r = m;
else l = m;
}
return l;
}
LL dp[300][301];
LL solve(int now, LL cost){
if(dp[now][cost] != -1) return dp[now][cost];
if(chi[now].size() == 0 && cost != 0) return dp[now][cost] = INT_MAX;
LL ans = 0;
for(int i=0; i<chi[now].size(); i++){
LL tmp = LLONG_MAX;
for(LL j=0; j<=300; j++){
if(j > cost) continue;
LL t = abs(cost-j - chi[now][i].second);
tmp = min(tmp, t + solve(chi[now][i].first, j));
}
ans += tmp;
}
return dp[now][cost] = ans;
}
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<N+M-1; i++){
int P;
LL C;
scanf("%d%lld", &P, &C);
P--;
edge[i+1].PB(MP(P, C));
edge[P].PB(MP(i+1, C));
}
par[0] = -1;
dfs(0, -1);
if(N == 1){
for(int i=0; i<N+M; i++){
node.PB(MP(depth(i), i));
}
sort(node.begin(), node.end());
reverse(node.begin(), node.end());
LL ans = 0;
for(int i=0; i<N+M; i++){
int now = node[i].second;
if(chi[now].size() == 0){
a[now] = 0;
b[now] = 0;
continue;
}
for(int j=0; j<chi[now].size(); j++){
a[chi[now][j].first] += chi[now][j].second;
b[chi[now][j].first] += chi[now][j].second;
}
LL tmp = sanbun(now);
LL nowAns = 0;
for(int j=0; j<chi[now].size(); j++){
if(tmp < a[chi[now][j].first]) nowAns += a[chi[now][j].first] - tmp;
else if(tmp > b[chi[now][j].first]) nowAns += tmp - b[chi[now][j].first];
}
ans += nowAns;
a[now] = my_binary_search(now, nowAns, tmp, -1);
b[now] = my_binary_search(now, nowAns, tmp, 1000000000LL*300000LL);
cout << nowAns << " " << a[now] << " " << b[now] << endl;
}
}
else{
for(int i=0; i<N+M; i++){
for(int j=0; j<=300; j++){
dp[i][j] = -1;
}
}
LL ans = LLONG_MAX;
for(int i=0; i<=300; i++){
//cout << solve(0, i) << endl;
ans = min(ans, solve(0, i));
}
cout << ans << endl;
}
}
Compilation message
fireworks.cpp: In function 'void dfs(int, int)':
fireworks.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int my_binary_search(int, long long int, long long int, long long int)':
fireworks.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<chi[now].size(); i++){
~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int func(int, long long int)':
fireworks.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<chi[now].size(); i++){
~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int solve(int, long long int)':
fireworks.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<chi[now].size(); i++){
~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<chi[now].size(); j++){
~^~~~~~~~~~~~~~~~
fireworks.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<chi[now].size(); j++){
~^~~~~~~~~~~~~~~~
fireworks.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld", &P, &C);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
22 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
24 ms |
14592 KB |
Output is correct |
| 4 |
Correct |
42 ms |
14728 KB |
Output is correct |
| 5 |
Correct |
37 ms |
14720 KB |
Output is correct |
| 6 |
Correct |
55 ms |
14692 KB |
Output is correct |
| 7 |
Correct |
48 ms |
14848 KB |
Output is correct |
| 8 |
Correct |
51 ms |
14848 KB |
Output is correct |
| 9 |
Correct |
48 ms |
14848 KB |
Output is correct |
| 10 |
Correct |
51 ms |
14964 KB |
Output is correct |
| 11 |
Correct |
63 ms |
14976 KB |
Output is correct |
| 12 |
Correct |
56 ms |
15096 KB |
Output is correct |
| 13 |
Correct |
61 ms |
15104 KB |
Output is correct |
| 14 |
Correct |
85 ms |
15200 KB |
Output is correct |
| 15 |
Correct |
71 ms |
15232 KB |
Output is correct |
| 16 |
Correct |
60 ms |
15100 KB |
Output is correct |
| 17 |
Correct |
65 ms |
15100 KB |
Output is correct |
| 18 |
Correct |
68 ms |
15104 KB |
Output is correct |
| 19 |
Correct |
85 ms |
15232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
