Submission #1005341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005341		vjudge1	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	2290 ms	2097152 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 = 5e4 + 5;
const int bmax = 16;

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]][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) {
         if(cb(sum[node][bit], req[node][bit]))
            node = p[node][bit];
         bit--;
      }
      return node;
   }
};

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

vector<Pointers> winners;
vector<int> limits;

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_;
   
   vector<int> losing(n, 1);
   map<int, vector<int>> times;
   for(int i = 0; i < n; i++)
      times[s[i]].emplace_back(i);
      
   for(auto &[cost, nexters] : times) {
      //cerr << cost << '\n';
      limits.emplace_back(cost);
      winners.emplace_back();
      for(int i = 0; i < n; i++) {
         if(losing[i]) winners.back().addlink(i, l[i], 0, p[i]);
         else winners.back().addlink(i, w[i], s[i], s[i]);
      }
      winners.back().addlink(n, n, 0, 0);
      for(auto x : nexters) losing[x] = 0;
   }
   
   
   limits.emplace_back((int)1e16);
   winners.emplace_back();
   for(int i = 0; i < n; i++) {
      if(losing[i]) winners.back().addlink(i, l[i], 0, p[i]);
      else winners.back().addlink(i, w[i], s[i], s[i]);
   }
   winners.back().addlink(n, n, 0, 0);
   
   for(auto &x : winners) x.cascade(n);
   return;
}

long long simulate(signed x_, signed z_) {
   ll z = z_, x = x_;
   int poz = 0;
   
   while(x != n) {
      while(z >= limits[poz]) poz++; 
      x = winners[poz].walk([&](ll sum, ll req) {
         bool rez = z >= req && z + sum < limits[poz];
         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]; } // ????
   }
   
   return z;
}

#undef int

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

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