제출 #993906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993906		cadmiumsky	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	컴파일 에러	0 ms	0 KiB

worst_reporter2

// o sa ia zero
#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 jump[nmax], p[nmax], d[nmax];
   int budget[nmax];
   
   void fill(int a, int f) {
      
      //cerr << a << ' ' << f << '\n';
      
      d[a] = d[f] + 1;
      p[a] = jump[a] = f;
      if(d[f] + d[jump[jump[f]]] == 2 * d[jump[f]]) jump[a] = jump[jump[f]];
            
      pin[a] = inp++;
      for(auto x : g[a])
         if(x != f) 
            fill(x, a);
      pout[a] = inp++;
      return;
   }

   void startProcedure(vector<int> nodes) {
      height[0] = -inf;
      sol = 0;
      inp = 1;
      fill(0, 0);
      
      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])];
      
      occupied.init(inp);
      
      //cerr << "wow\n";
      
      ll sum = 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 | views::take(sz(nodes) - 1)) {
         //cerr << x << '\t' << anc(x) << '\t' << height[x] << '\n';
         int mine = anc(x), upward = x, mybudget = cost[x];
         
         while(mybudget > 0 && mine > 0) {
            int tmp = upward;
            //if(mine >= 0) cerr << upward << '\t';
            while(upward != 0 && anc(upward) == mine) {
               if(anc(jump[upward]) == mine) upward = jump[upward];
               tmp = upward;
               upward = p[upward];
            }
            upward = tmp;
            //if(mine >= 0) cerr << upward << '\n';
            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];
      }
      
      sol = sum - sol;
      
      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;
      g[n + 1].clear(); g[0].clear();
      g[0].emplace_back(n + 1); g[n + 1].emplace_back(0);
      nodes.emplace_back(0); nodes.emplace_back(n + 1);
      
      int x = i;
      while(solved[x] == 0) {
         solved[x] = -1;
         x = father[x];
      }
      int mnh = height[x];
      while(solved[x] == -1) {
         solved[x] = -2;
         mnh = min(mnh, height[x]);
         x = father[x];
      }
      
      
      height[n + 1] = mnh;
      cost[n + 1] = 0;
      while(solved[x] == -2) {
         if(height[x] != height[n + 1]) autoAdd += cost[x];
         else cost[n + 1] += cost[x];
         
         for(auto a : naive[x]) {
            if(solved[a] != -2 && solved[a] != 1) {
               fill(a, x, [&](int node) {
                  nodes.emplace_back(node);
                  if(solved[father[node]] == -2) 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];
      }
      
      //for(auto x : nodes) cerr << x << ' ';
      //cerr << '\n';
      //cerr << autoAdd << '\n';
      DS::startProcedure(nodes);
      autoAdd += DS::sol;
   }
   
   cout << autoAdd << '\n';
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

컴파일 시 표준 에러 (stderr) 메시지

worst_reporter2.cpp: In function 'void DS::startProcedure(std::vector<long long int>)':
worst_reporter2.cpp:96:28: error: 'views' has not been declared
   96 |       for(auto x : nodes | views::take(sz(nodes) - 1)) {
      |                            ^~~~~
worst_reporter2.cpp:100:16: error: 'mybudget' was not declared in this scope; did you mean 'budget'?
  100 |          while(mybudget > 0 && mine > 0) {
      |                ^~~~~~~~
      |                budget
worst_reporter2.cpp:101:23: error: 'upward' was not declared in this scope
  101 |             int tmp = upward;
      |                       ^~~~~~
worst_reporter2.cpp:117:17: error: 'mybudget' was not declared in this scope; did you mean 'budget'?
  117 |          sol += mybudget;
      |                 ^~~~~~~~
      |                 budget