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 int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3uHasSr ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
const int inf=1e18;
signed main(){
_3uHasSr;
int n;
cin>>n;
vec(pii) a(n+1);
vi g(n+1);
vec(vi) rg(n+1);
rep(i,n){
int u,h,c;
cin>>u>>h>>c;
u-=1;
g[i]=u;
rg[u].pb(i);
a[i]={h,c};
}
vec(std::map<int,int>) dp(n+1);
vi center(n+1);
rep(v,n+1){
center[v]=v;
}
auto evaluate=[&](int rt,vi&usd){
vi topo;
{
queue<int> que;
que.push(rt);
while(sz(que)){
int v=que.front();
que.pop();
topo.pb(v);
for(auto u:rg[v]){
que.push(u);
}
}
}
for(auto v:topo){
usd[v]=1;
// print(v);
}
per(i,sz(topo)){
int v=topo[i];
auto [h,c]=a[v];
dp[center[v]][h]+=c;
// perform dp update
{
auto it=dp[center[v]].find(h);
if(it!=dp[center[v]].begin()){
it=prev(it);
while(1){
auto nit=it;
bool lok=0;
if(it==dp[center[v]].begin()){
lok=1;
}else{
it=prev(it);
}
pii _p=*nit;
if(c>=_p.se){
c-=_p.se;
dp[center[v]].erase(nit);
}else{
_p.se-=c;
dp[center[v]].erase(nit);
dp[center[v]][_p.fi]+=_p.se;
break;
}
if(lok){
break;
}
}
}
}
if(!i){
break;
}
// merge to parent node
int up=g[v];
int u0=center[up],u1=center[v];
if(sz(dp[u0])<sz(dp[u1])){
swap(u0,u1);
center[up]=center[v];
}
for(auto p:dp[u1]){
dp[u0][p.fi]+=p.se;
}
}
int v=center[topo[0]];
vec(pii) evs;
for(auto p:dp[v]){
if(p.fi){
evs.pb(p);
}
}
per(i,sz(evs)-1){
evs[i].se+=evs[i+1].se;
}
return evs;
};
const int extra_node=n;
vi usd(n+1),incyc(n+1);
int res=0;
rep(rt,n){
if(usd[rt]){
continue;
}
vi way,cyc;
{
int v=rt;
while(1){
way.pb(v);
int u=g[v];
if(usd[u]){
while(way.back()!=u){
cyc.pb(way.back());
way.pop_back();
}
cyc.pb(way.back());
way.pop_back();
reverse(cyc.begin(), cyc.end());
break;
}
usd[v]=1;
v=u;
}
for(auto v:cyc){
incyc[v]=1;
}
}
vi rbts;
{
for(auto v:cyc){
for(auto u:rg[v]){
if(!incyc[u]){
rbts.pb(u);
}
}
}
}
// // unite cycle and add edge from every rabbit to extra
{
rg[extra_node].clear();
dp[extra_node].clear();
g[extra_node]=0;
center[extra_node]=extra_node;
}
for(auto v:rbts){
g[v]=extra_node;
rg[extra_node].pb(v);
}
vec(pii) evs=evaluate(extra_node,usd);
int now=evs[0].se;
std::map<int,int> mp;
for(auto v:cyc){
mp[a[v].fi]+=a[v].se;
}
for(auto p:mp){
int need=p.fi;
auto it=lower_bound(evs.begin(), evs.end(),pii(need,-1));
if(it==evs.end()){
now=max(now,p.se);
}else{
now=max(now,p.se+(*it).se);
}
}
res+=now;
}
rep(v,n){
res-=a[v].se;
}
print(-res);
//
return 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... |