Submission #1005312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005312		vjudge1	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	9 ms	13404 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 = 5e5 + 5;
const int bmax = 25;

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> int walk(CB&& cb, int node) {
      int bit = 0;
      while(bit < bmax && cb(sum[node][bit], req[node][bit])) {
         node = p[node][bit];
         bit++;
      }
      bit--;
      while(bit >= 0 && cb(sum[node][bit], req[node][bit])) {
         node = p[node][bit];
         bit--;
      }
      return node;
   }
};

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

Pointers winners;

void init(signed n_, std::vector<signed> s_, std::vector<signed> p_, std::vector<signed> w_, std::vector<signed> 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(signed x_, signed z_) {
   ll z = z_, x = x_;
   
   while(x != n) {
      x = winners.walk([&](ll sum, ll req) {
         bool rez = z >= req;
         if(rez) z += sum;
         return rez;
      }, x);
      if(x == n) break;
      if(s[x] > z) { z += p[x]; x = l[x]; }
      else { z += s[x]; x = w[x]; assert(false); } // ????
   }
   
   return z;
}

#undef int

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

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