#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,a,b) for(int i(a);i<=(b);i++)
#define repr(i,a,b) for(int i(a);i>=(b);i--)
using namespace std;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int n,m;
int p[300010],c[300010];
ll ans[300010],up[300010];
vi adj[300010];
priority_queue<ll>* pq[300010];
void merge(int u,int v) {
while(!pq[v]->empty()) {
int x=pq[v]->top();pq[v]->pop();
if(x>up[u]) {
pq[u]->push(up[u]);
ans[u]+=x-up[u];
up[u]=x;
} else {
pq[u]->push(x);
}
}
if(pq[u]->top()<=up[v]&&up[v]<up[u]) {
up[u]=up[v];
} else if(up[v]<pq[u]->top()) {
up[u]=pq[u]->top();
ans[u]+=pq[u]->top()-up[v];
pq[u]->pop();
pq[u]->push(up[v]);
}
ans[u]+=ans[v];
}
void adjust(int u) {
up[u]+=c[u];
int top=pq[u]->top();
pq[u]->pop();
pq[u]->push(top+c[u]);
}
void debug(int u) {
priority_queue<int> b;
cout<<"u:"<<u<<",ans:"<<ans[u]<<",up:"<<up[u]<<",pq:";
while(!pq[u]->empty())b.push(pq[u]->top()),pq[u]->pop();
while(!b.empty()) {
ll it=b.top();b.pop();
cout<<it<<' ';
pq[u]->push(it);
}cout<<endl;
}
void solve(int u) {
if(adj[u].empty()) {
pq[u]=new priority_queue<ll>();
pq[u]->push(0);
up[u]=0;
return;
}
int mx=0,id=0;
for(auto& it:adj[u]) {
solve(it);
adjust(it);
if(mx<sz((*pq[it]))) {
mx=sz((*pq[it]));
id=it;
}
}
for(auto& it:adj[u]) {
if(it==id)continue;
merge(id,it);
//debug(id);
}
pq[u]=pq[id];
ans[u]=ans[id];
up[u]=up[id];
//debug(u);
}
void MAIN() {
int i,j;
cin>>n>>m;
for(i=2;i<=n+m;i++) {
cin>>p[i]>>c[i];
adj[p[i]].pb(i);
}
solve(1);
cout<<ans[1];
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);
int T=1;
//cin>>T;
for(int tt=1;tt<=T;tt++) {
MAIN();
}
return 0;
}
Compilation message
fireworks.cpp: In function 'void _dmp(const char*, TH, TA ...)':
fireworks.cpp:20:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
^~~~~
fireworks.cpp:20:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
^~~~
fireworks.cpp: In function 'void MAIN()':
fireworks.cpp:98:8: warning: unused variable 'j' [-Wunused-variable]
int i,j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
