Submission #887882

#	Time	Username	Problem	Language	Result	Execution time	Memory
887882		nguyentunglam	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7101 ms	1082188 KiB

dungeons

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 4e5 + 10, M = 23;

int gain[9][M + 1][N];

int can_win[9][M + 1][N];

int go[9][M + 1][N];

int base[20];

int group[10000010];

int s[N], p[N], w[N], l[N];

int n;

void init(int _n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
  n = _n;

  for(int i = 0; i < n; i++) {
    s[i] = S[i];
    p[i] = P[i];
    w[i] = W[i];
    l[i] = L[i];
  }

  base[0] = 1;
  for(int i = 1; i <= 10; i++) base[i] = base[i - 1] * 8;


  for(int i = 1; i <= 1e7; i++) {
    group[i] = group[i - 1];
    if (i >= base[group[i] + 1]) group[i]++;
  }

  for(int j = 0; j <= 8; j++) {
    for(int i = 0; i < n; i++) {
      if (group[s[i]] < j) {
        go[j][0][i] = w[i];
        gain[j][0][i] = s[i];
        can_win[j][0][i] = 1e9;
      }
      else {
        go[j][0][i] = l[i];
        gain[j][0][i] = p[i];
        can_win[j][0][i] = s[i];
      }
    }
    for(int k = 1; k <= M; k++) for(int i = 0; i < n; i++) {
      int nxt = go[j][k - 1][i];
      if (nxt == n) {
        go[j][k][i] = go[j][k - 1][i];
        gain[j][k][i] = gain[j][k - 1][i];
        can_win[j][k][i] = can_win[j][k - 1][i];
      }
      else {
        go[j][k][i] = go[j][k - 1][nxt];
        gain[j][k][i] = gain[j][k - 1][i] + gain[j][k - 1][nxt];
        can_win[j][k][i] = min(can_win[j][k - 1][i], can_win[j][k - 1][nxt] - gain[j][k - 1][i]);
      }
    }
  }

	return;
}

long long simulate(int x, int _z) {
  long long z = _z;
  while (x != n) {
    int j = z >= 1e7 ? 8 : group[z];
    for(int k = M; k >= 0; k--) {
      if (z >= can_win[j][k][x]) continue;
      z += gain[j][k][x];
      x = go[j][k][x];
      if (x == n) return z;
    }
    if (z >= s[x]) {
      z += s[x];
      x = w[x];
    }
    else {
      z += p[x];
      x = l[x];
    }
  }
  return z;
}


#ifdef ngu
int32_t main() {

  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  int n, q; cin >> n >> q;

  vector<int> s(n), p(n), w(n), l(n);

  for(int i = 0; i < n; i++) cin >> s[i];
  for(int i = 0; i < n; i++) cin >> p[i];
  for(int i = 0; i < n; i++) cin >> w[i];
  for(int i = 0; i < n; i++) cin >> l[i];

  init(n, s, p, w, l);

  while (q--) {
    int x, z; cin >> x >> z;
    cout << simulate(x, z) << endl;
  }
}
#endif // ngu

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