Submission #1230762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230762		rxlfd314	Dungeons Game (IOI21_dungeons)	C++20	62 / 100	7095 ms	168744 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 = 30;
vt<int> S, P, W, L;
int N, subtask;
int tree_lift[mxN][LOG+1];
ll tree_lift_val[mxN][LOG+1];
ll depth[mxN];
vt<int> vals;
int lift[5][mxN][LOG+1];
ll lift_val[5][mxN][LOG+1];

ll simulate(int i, int zz) {
  ll z = zz;
  if (subtask == 2) {
    while (i != N) {
      int cur = i;
      ROF(j, LOG, 0)
        if (depth[i] + z >= tree_lift_val[cur][j])
          cur = tree_lift[cur][j];
      z += depth[i] - depth[cur] + P[cur];
      i = L[cur];
    }
    return z;
  }
  if (subtask == 4) {
    FOR(x, 0, size(vals)-1) {
      ROF(j, LOG, 0)
        if (z + lift_val[x][i][j] < vals[x]) {
          z += lift_val[x][i][j];
          i = lift[x][i][j];
        }
      if (z < vals[x]) {
        if (z < S[i]) {
          z += P[i];
          i = L[i];
        } else {
          z += S[i];
          i = W[i];
        }
      }
    }
    return z + depth[i] - depth[N];
  }
  while (i != N) {
    if (z < S[i]) {
      z += P[i];
      i = L[i];
    } else {
      z += S[i];
      i = W[i];
    }
  }
  return z;
}

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;
  bool sub2 = true;
  FOR(i, 0, N-1)
    sub2 &= S[i] == P[i];
  S.push_back(0);
  P.push_back(0);
  W.push_back(N);
  L.push_back(N);
  ROF(i, N, 0) {
    depth[i] = depth[W[i]] + S[i];
    tree_lift[i][0] = W[i];
    tree_lift_val[i][0] = S[i] + depth[i];
  }
  if (sub2) {
    subtask = 2;
    FOR(j, 1, LOG)
      FOR(i, 0, N) {
        tree_lift[i][j] = tree_lift[tree_lift[i][j-1]][j-1];
        tree_lift_val[i][j] = max(tree_lift_val[tree_lift[i][j-1]][j-1], tree_lift_val[i][j-1]);
      }
    #ifdef DEBUG
    cout << "subtask = 2\n";
    #endif
    return;
  }
  vals = S;
  sort(all(vals));
  vals.erase(unique(all(vals)), vals.end());
  if (size(vals) <= 5) {
    subtask = 4;
    FOR(x, 0, size(vals)-1) {
      FOR(i, 0, N) {
        if (S[i] >= vals[x]) {
          lift[x][i][0] = L[i];
          lift_val[x][i][0] = P[i];
        } else {
          lift[x][i][0] = W[i];
          lift_val[x][i][0] = S[i];
        }
      }
      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];
        }
    }
    #ifdef DEBUG
    cout << "subtask = 4\n";
    #endif
    return;
  }
  #ifdef DEBUG
  cout << "subtask = 1\n";
  #endif
}

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