This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
const ll inf=1e18;
vec<int> g[N];
int c[N],a[N],h[N];
ll toadd=0;
map<int,ll> mp;
int cnt[N];
vec<pil> *dps[N];
int dp1[N];
//ll sm[N]
void dfs1(int v){
dp1[v]=1;
for(auto &z : g[v]){
dfs1(z);
dp1[v]+=dp1[z];
}
}
void dfs(int v,bool keep=0){
// cout<<"DFS "<<v<<' '<<h[v]<<endl;
int big=-1;
for(auto &z : g[v]){
if(big==-1 || dp1[z]>dp1[big])
big=z;
}
for(auto &z : g[v]){
if(z==big) continue;
dfs(z,0);
}
if(big!=-1){
dfs(big,1);
// dps[v]=dps[big];
}
// else{
dps[v]=new vec<pil>();
// }
for(auto &z : g[v]){
if(z==big) continue;
int last=0;
for(auto &u : *dps[z]){
mp[u.f]+=u.s;
}
(*dps[z]).clear();
}
mp[h[v]]-=c[v];
mp[h[v]+1]+=c[v];
mp[0]+=c[v];
// cerr<<"HEY "<<mp[h[v]]<<endl;
while(mp[h[v]]<=0){
auto it=mp.lower_bound(h[v]);
if(it==mp.begin()) break;
--it;
mp[h[v]]+=it->s;
mp.erase(it);
}
// for(auto &z : mp)
// cout<<"DELT "<<v<<' '<<z.f<<' '<<z.s<<endl;
if(!keep){
for(auto &u : mp){
(*dps[v]).pb(u);
}
mp.clear();
}
}
signed main(){
fast_resp;
int n;
cin>>n;
vec<int>kek;
for(int i=0;i<n;i++){
cin>>a[i]>>h[i]>>c[i];--a[i];
if(a[i]!=i) g[a[i]].pb(i);
kek.pb(h[i]);
}
// sort(all(kek));kek.erase(unique(all(kek)),kek.end());
//// dp1[N]=inf;
// for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin();
dfs1(0);dfs(0);
ll sm=0;
for(auto &z : (*dps[0])){
sm+=z.s;
if(z.f>0){
cout<<sm<<endl;
return 0;
}
}
assert(false);
// cout<<sm;
return 0;
}
/*
2
1 89 964898447
2 20 952129455
*/
Compilation message (stderr)
worst_reporter2.cpp: In function 'void dfs(long long int, bool)':
worst_reporter2.cpp:60:13: warning: unused variable 'last' [-Wunused-variable]
60 | int last=0;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |