Submission #417117

#	Time	Username	Problem	Language	Result	Execution time	Memory
417117		kai824	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	13 ms	14992 KiB

worst_reporter2

//tree subtasks: slope trick haha...
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define f first
#define s second

int h[200005],c[200005];
vector<int> adjl[200005];

int delt[200005];
map<int,int> ss[200005];
map<int,int>::iterator it;

int nd;
void dfs(int node,int p=-1,bool r=false){
  ss[node].clear();delt[node]=0;

  for(int x:adjl[node]){
    if(x==p)continue;
    dfs(x,node);
  }
  nd=node;
  for(int x:adjl[node]){
    if(x==p)continue;
    if(ss[x].size()>=ss[nd].size())nd=x;
  }
  if(nd!=node){
    swap(ss[nd],ss[node]);
    swap(delt[nd],delt[node]);
  }
  for(int x:adjl[node]){
    if(x==p)continue;
    for(pii hm:ss[x]){
      ss[node][hm.f]+=hm.s;
    }
    ss[x].clear();
    delt[node]+=delt[x];
  }
  //add node value...
  delt[node]+=c[node];
  if(r){
    ss[node][h[node]]+=c[node];
    ss[node][h[node]-1]-=c[node];
  }else{
    it=ss[node].upper_bound(h[node]);
    int cur=0;
    while(true){
      if(it==ss[node].begin())break;
      it--;
      if(cur+it->s<=c[node]){
        cur+=it->s;
        it=ss[node].erase(it);
      }else{
        ss[node][it->f]=cur+it->s-c[node];
        break;
      }
    }
    ss[node][h[node]]+=c[node];
  }
}

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int n;
  cin>>n;

  int a;
  for(int i=1;i<=n;i++){
    cin>>a>>h[i]>>c[i];
    if(i>1)adjl[a].push_back(i);
  }
  dfs(1,-1,true);
  int ans=delt[1],cur=delt[1];
  for(it=ss[1].end();it!=ss[1].begin();){
    it--;
    cur-=it->s;
    ans=min(ans,cur);
  }
  cout<<ans;
  return 0;
}
/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21