Submission #993915

#	Time	Username	Problem	Language	Result	Execution time	Memory
993915		cadmiumsky	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	645 ms	100428 KiB

worst_reporter2

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
 
using ll = long long;
using ld = long double;
 
#define int ll
#define sz(x) ((int)(x).size())
 
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
 
const int nmax = 2e5 + 5;
const int inf = 1e9 + 5 + 7 + 9;

vector<int> g[nmax];
 
int father[nmax], cost[nmax], height[nmax];
vector<int> naive[nmax];
 
int solved[nmax];
 
template<class CB> void fill(int a, int f, CB&& cb, vector<int> graph[nmax]) {
   cb(a);
   for(auto x : graph[a])
      if(x != f) 
         fill(x, a, cb, graph);
   return;
}
 
#define lsb(x) (x & -x)
struct AIB {
   vector<int> v;
   void init(int n_) { v.assign(n_ + 5, 0); }
   int query(int a) {
      int sum = 0;
      while(a > 0) sum += v[a], a -= lsb(a);
      return sum;
   }
   void update(int p, int x) {
      while(p < sz(v)) v[p] += x, p += lsb(p);
   }
};
 
namespace DS {
   ll sol;
  
   AIB occupied;
   int pin[nmax], pout[nmax], inp;
   int p[nmax][18], d[nmax];
   int budget[nmax];
   
   void fill(int a, int f) {
      
      //cerr << a << ' ' << f << '\n';
      
      d[a] = d[f] + 1;
      p[a][0] = f;
      for(int i = 1; i < 18; i++) p[a][i] = p[p[a][i - 1]][i - 1];
      
      pin[a] = inp++;
      for(auto x : g[a])
         if(x != f) 
            fill(x, a);
      pout[a] = inp;
      return;
   }
 
   void startProcedure(vector<int> nodes, vector<int> cycles) {
      height[0] = -inf;
      sol = 0;
      inp = 1;
      fill(0, 0);
      
      map<int, ll> cyclefree;
      
      for(auto x : cycles) solved[x] = 100, d[x] = -1;
      copy(all(cycles), back_inserter(nodes));
      
      map<pii, int> renrm;
      for(auto x : nodes) renrm[make_pair(height[x], d[x])];
      int cnt = 0;
      for(auto &[a, b] : renrm) b = cnt++;
      for(auto x : nodes) height[x] = renrm[make_pair(height[x], d[x])];
      for(auto x : nodes) {
         if(solved[x] == 100)
            cyclefree[height[x]] += cost[x];
      }
      
      occupied.init(inp);
      
      //cerr << "wow\n";
      
      ll sum = 0, maxpossible = 0;
      for(auto x : nodes) sum += cost[x];
      
      sort(all(nodes), [&](int a, int b) { return height[a] > height[b]; });
      for(auto x : nodes) budget[x] = 0;
      
      auto anc = [&](int node) { return occupied.query(pin[node]); };
      auto modnode = [&](int node, int p) { occupied.update(pin[node], p), occupied.update(pout[node], -p); };
      
      for(auto x : nodes) {
         int specialed = 0;
         if(solved[x] == 100) {
            specialed = cyclefree[height[x]];
         }
         else {
            int mine = anc(x), upward = x, mybudget = cost[x];
            
            while(mybudget > 0 && mine > 0) {
               for(int i = 31 - __builtin_clz(d[upward] + 2); i >= 0; i--)
                  if(anc(p[upward][i]) == mine) upward = p[upward][i];
               if(upward != 0) {
                  int u = min(mybudget, budget[upward]);
                  mybudget -= u, budget[upward] -= u;
                  if(budget[upward] == 0) modnode(upward, -1), mine = anc(x);
               }
            }
            
            sol += mybudget;
            
            modnode(x, 1);
            budget[x] = cost[x];
         }
         
         maxpossible = max(maxpossible, sol + specialed);
      }
      
      for(auto x : nodes) solved[x] = 1;
      
      sol = sum - maxpossible;
      
      return;
   }
}
 
signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;
   
   for(int i = 1; i <= n; i++) {
      cin >> father[i] >> height[i] >> cost[i];
      naive[i].emplace_back(father[i]);
      naive[father[i]].emplace_back(i);
   }
   
   ll autoAdd = 0;
   
   for(int i = 1; i <= n; i++) {
      if(solved[i]) continue;
      
      vector<int> nodes, cycles;
      g[n + 1].clear(); g[0].clear();
      g[0].emplace_back(n + 1); g[n + 1].emplace_back(0);
      
      int x = i;
      while(solved[x] == 0) {
         solved[x] = -2;
         x = father[x];
      }
      while(solved[x] == -2) {
         solved[x] = -1;
         x = father[x];
      }
      
      height[n + 1] = -inf;
      cost[n + 1] = 0;
      while(solved[x] == -1) {
         cycles.emplace_back(x);
         
         for(auto a : naive[x]) {
            if(solved[a] != -1 && solved[a] != 1) {
               fill(a, x, [&](int node) {
                  nodes.emplace_back(node);
                  if(solved[father[node]] == -1) g[node].emplace_back(n + 1), g[n + 1].emplace_back(node);
                  else g[node].emplace_back(father[node]), g[father[node]].emplace_back(node);
                  solved[node] = 1;
               }, naive);
            }
         }
         solved[x] = 1;
         x = father[x];
      }
      
      DS::startProcedure(nodes, cycles);
      autoAdd += DS::sol;
   }
   
   cout << autoAdd << '\n';
}
 
/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/
 

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