Submission #1005303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005303		vjudge1	던전 (IOI21_dungeons)	C++17	11 / 100	7059 ms	145832 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.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 = 4e5 + 5;
const int bmax = 19;

struct Pointers {
   int p[nmax][bmax];
   ll sum[nmax][bmax];
   int req[nmax][bmax];
   
   void addlink(int node, int p_, int req_, int gain_) {
      p[node][0] = p_;
      sum[node][0] = gain_;
      req[node][0] = req_;
   }
   
   
   void cascade(int n) {
      for(int step = 1; step < bmax; step++) {
         for(int i = 0; i <= n; i++) {
            p[i][step] = p[p[i][step - 1]][step - 1];
            sum[i][step] = sum[i][step - 1] + sum[p[i][step - 1]][step - 1];
            req[i][step] = max({0LL, (ll)req[i][step - 1], (ll)req[p[i][step - 1]] - sum[i][step - 1]});
            //cerr << p[i][step] << ' ';
         }
      }
      return;
   }
   
   template<class CB> void walk(CB&& cb, int& node, ll& z) {
      int bit = 0;
      while(bit < bmax && cb(sum[node][bit], req[node][bit])) {
         //cerr << node << " -> " << p[node][bit] << ", " << sum[node][bit] << '\n';
         z += sum[node][bit];
         node = p[node][bit];
         bit++;
      }
      bit--;
      while(bit >= 0 && cb(sum[node][bit], req[node][bit])) {
         z += sum[node][bit];
         node = p[node][bit];
         bit--;
      }
      return;
   }
};

namespace {
   vector<int> s, p, w, l;
   int n;
}

Pointers winners;

void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
   n = n_;
   s = s_;
   p = p_;
   w = w_;
   l = l_;
   
   for(int i = 0; i < n; i++) winners.addlink(i, w[i], s[i], s[i]);
   winners.addlink(n, n, 0, 0);
   winners.cascade(n);
   return;
}

long long simulate(int x, int z_) {
   ll z = z_;
   
   while(x != n) {
      //cerr << "win streak: " << x << ", " << z << " --> ";
      winners.walk([&](ll sum, ll req) {
         return z >= req;
      }, x, z);
      //cerr << x << ", " << z << '\n';
      if(x == n) break;
      if(s[x] > z) { z += p[x]; x = l[x]; }
      else { z += s[x]; x = w[x]; } // ????
   }
   
   return z;
}



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

• Subtask 1: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11