Submission #1198338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198338		mychecksedad	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	100 / 100	372 ms	175828 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 = 4e5+100, M = 1e5+10, K = 52, MX = 30;


int n;
vi g[N];
array<ll, 2> a[N];
multiset<array<ll, 2>> dp[N];
vector<array<ll, 2>> rootss[N];
int root;
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){
    if(v != root){
      dp[v].insert(array<ll, 2>{a[v][0] + 1, a[v][1]});
    }else{
      for(auto [h, c]: rootss[root]){
        dp[v].insert(array<ll, 2>{h, 0});
      }
    }
    return;
  }
  dp[v].swap(dp[big]);
  for(int u: g[v]){
    if(u != big){
      for(auto x: dp[u]) dp[v].insert(x);
    }
  }
  if(v != root){
    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});
    }
  }else{
    for(auto [h, c]: rootss[root]){
      dp[v].insert(array<ll, 2>{h, 0});
    }
  }
}

void solve(){
  cin >> n;
  vi p(n + 1);
  for(int i = 1; i <= n; ++i){
    cin >> p[i];
    cin >> a[i][0] >> a[i][1];
  }
  vi vis(n+1);
  vi in_loop(n+1);
  vector<vi> roots;
  for(int i = 1; i <= n; ++i){
    in_loop[i] = i;
  }
  for(int i = 1; i <= n; ++i){
    if(!vis[i]){
      int v = i;
      stack<int> st;
      while(!vis[v]){
        st.push(v);
        vis[v] = 1;
        v = p[v];
      }
      // cout << v << ' ';
      bool any_lop = false;
      vi loop;
      while(st.size()){
        loop.pb(st.top());
        if(v == st.top()){
          any_lop = true;
          break;
        }
        st.pop();
      }
      if(any_lop){
        int id = roots.size() + 1;
        roots.pb(loop);
        for(int x: loop){
          in_loop[x] = id + n;
        }
      }
    }
  }
  for(int i = 1; i <= n; ++i){
    if(in_loop[i] > n){
      // nothing
      rootss[in_loop[i]].pb({a[i][0], a[i][1]});
    }else{
      g[in_loop[p[i]]].pb(i);
    }
  }
  ll ans = 0;
  for(int i = n + 1; i <= n + roots.size(); ++i){
    root = i;
    dfs(i);
    int v = i;
    ll cost = 0, cur = 1e18;
    map<int, ll> COST;
    for(auto [h, c]: rootss[i]) cost += c, COST[h] -= c;
    dp[v].insert(array<ll, 2>{0, 0});
    int last = 0;
    for(auto val: dp[v]){
      if(last != val[0]){
        cur = min(cur, cost + COST[last]);
      }
      cost += val[1];
      last = val[0];
    }
    cur = min(cur, cost + COST[last]);
    ans += cur;
  }
  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: 21 / 21