Submission #1232910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232910		rxlfd314	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	4886 ms	1784408 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 400005, LOG = 24, LLOG = 8;
vt<int> S, P, W, L;
int N;
int lift[LLOG+1][mxN][LOG+1];
ll lift_val[LLOG+1][mxN][LOG+1];
ll lift_cap[LLOG+1][mxN][LOG+1];
ll depth[mxN];

ll simulate(int i, int zz) {
  ll z = zz;
  FOR(x, 0, LLOG) {
    while (i != N && z < 1 << 3*(x+1)) {
      ROF(j, LOG, 0)
        if (z < lift_cap[x][i][j]) {
          z += lift_val[x][i][j];
          i = lift[x][i][j];
        }
      z += S[i];
      i = W[i];
    }
  }
  return z + depth[i];
}

void init(int _N, vt<int> _S, vt<int> _P, vt<int> _W, vt<int> _L) {
  N = _N, S = _S, P = _P, W = _W, L = _L;
  S.push_back(0);
  P.push_back(0);
  W.push_back(N);
  L.push_back(N);
  ROF(i, N-1, 0)
    depth[i] = depth[W[i]] + S[i];
  FOR(x, 0, LLOG) {
    FOR(i, 0, N) {
      if (S[i] > 1 << 3*x) {
        lift[x][i][0] = L[i];
        lift_val[x][i][0] = P[i];
        lift_cap[x][i][0] = S[i];
      } else {
        lift[x][i][0] = W[i];
        lift_val[x][i][0] = S[i];
        lift_cap[x][i][0] = LLONG_MAX;
      }
    }
    FOR(j, 1, LOG) 
      FOR(i, 0, N) {
        lift[x][i][j] = lift[x][lift[x][i][j-1]][j-1];
        lift_val[x][i][j] = lift_val[x][lift[x][i][j-1]][j-1] + lift_val[x][i][j-1];
        lift_cap[x][i][j] = min(lift_cap[x][i][j-1], lift_cap[x][lift[x][i][j-1]][j-1] - lift_val[x][i][j-1]);
      }
  }
}

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