Submission #1198330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198330		mychecksedad	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	79 / 100	337 ms	140988 KiB

worst_reporter2

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e5+100, M = 1e5+10, K = 52, MX = 30;


int n;
vi g[N];
array<ll, 2> a[N];
multiset<array<ll, 2>> dp[N];
void dfs(int v){
  int big = -1;
  for(int u: g[v]){
    dfs(u);
    if(big == -1 || dp[u].size() > dp[big].size()) big = u;
  } 
  if(big == -1){
    dp[v].insert(array<ll, 2>{a[v][0] + 1, a[v][1]});
    return;
  }
  dp[v].swap(dp[big]);
  for(int u: g[v]){
    if(u != big){
      for(auto x: dp[u]) dp[v].insert(x);
    }
  }
  dp[v].insert(array<ll, 2>{0, a[v][1]});
  dp[v].insert(array<ll, 2>{a[v][0] + 1, a[v][1]});



  auto it = dp[v].upper_bound(array<ll, 2>{a[v][0] + 1, -1});
  ll C = a[v][1];
  while(it != dp[v].begin() && C){
    it = prev(it);
    ll val = (*it)[1];
    assert((*it)[0] <= a[v][0]);
    if(val <= C){
      C -= val;
      dp[v].erase(it);
    }else{
      auto p = *it;
      dp[v].erase(it);
      dp[v].insert(array<ll, 2>{p[0], val - C});
      C = 0;
    }
    it = dp[v].upper_bound(array<ll, 2>{a[v][0] + 1, -1});
  }
}

void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    int x; cin >> x;
    if(x < i)
      g[x].pb(i);
    cin >> a[i][0] >> a[i][1];
  }
  dfs(1);
  ll ans = 0;
  auto it = dp[1].begin();
  while(it != dp[1].end() && (*it)[0] == 0){
    ans += (*it)[1];
    ++it;
  }
  cout << ans;
}



int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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