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);
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];
int tt=1;
struct segtree{
ll t[20*N],p[20*N];
int l[20*N],r[20*N];
ll d1,d2;
segtree(){
t[0]=0;
fill(t,t+20*N,0);
fill(l,l+20*N,0);
fill(r,r+20*N,0);
fill(p,p+20*N,0);
}
void push(int v,int tl,int tr){
if(!p[v])
return;
if(!l[v]) l[v]=tt++;
if(!r[v]) r[v]=tt++;
assert(tt<20*N);
for(auto &u : {l[v],r[v]})
p[u]+=p[v],t[u]+=p[v];
p[v]=0;
return;
}
void upd(int i,ll x,int &v,int tl=0,int tr=N-1){
if(!v)
v=tt++;
assert(tt<20*N);
if(tl==tr){
t[v]=x;
return;
}
int tm=(tl+tr)>>1;push(v,tl,tr);
if(tm>=i)
upd(i,x,l[v],tl,tm);
else
upd(i,x,r[v],tm+1,tr);
t[v]=min(t[l[v]],t[r[v]]);
}
ll get(int l1,int r1,int v,int tl=0,int tr=N-1){
if(!v || tl>r1 || tr<l1)
return 0;
if(tl>=l1&&tr<=r1)
return t[v];
int tm=(tl+tr)>>1;push(v,tl,tr);
return min(get(l1,r1,l[v],tl,tm),get(l1,r1,r[v],tm+1,tr));
}
int mg(int v,int u,int tl,int tr){
if(!v && !u)
return 0;
if(tl==tr){
umin(d1,t[v]);umin(d2,t[u]);
if(!v){
t[u]=d1+d2;
return u;
}
t[v]=d1+d2;
return v;
}
if(!v){
umin(d2,t[u]);
p[u]+=d1;
t[u]+=d1;
return u;
}
if(!u){
umin(d1,t[v]);
p[v]+=d2;
t[v]+=d2;
return v;
}
int tm=(tl+tr)>>1;
if(l[u] || r[u]) push(u,tl,tr);
if(l[v] || r[v]) push(v,tl,tr);
p[v]=p[u]=0;
r[v]=mg(r[v],r[u],tm+1,tr);
l[v]=mg(l[v],l[u],tl,tm);
t[v]=d1+d2;
return v;
}
int Merge(int v,int u){
d1=d2=0;
return mg(v,u,0,N-1);
}
}sega;
ll toadd=0;
//map<int,ll> mp;
int root[N];
void dfs(int v){
// cout<<"DFS "<<v<<endl;
for(auto &z : g[v]){
dfs(z);
root[v]=sega.Merge(root[v],root[z]);
// cerr<<"EBAL "<<root[v]<<endl;
}
// cout<<"W "<<root[v]<<endl;
// cout<<sega.get(roo)
// cout<<"HEY "<<sega.get(root[v],h[v],N-1)<<endl;
sega.upd(h[v],sega.get(h[v],N-1,root[v])-c[v],root[v]);
}
signed main(){
fast_resp;
int n;
cin>>n;
vec<int>kek;
ll sm=0;
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]);sm+=c[i];
}
sort(all(kek));kek.erase(unique(all(kek)),kek.end());
for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin();
dfs(0);
cout<<sm+sega.get(0,N-1,root[0]);
return 0;
}
/*
3
1 3 6
1 2 5
1 5 6
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
2
1 89 964898447
2 20 952129455
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |