제출 #887888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887888		nguyentunglam	던전 (IOI21_dungeons)	C++17	100 / 100	1627 ms	1423444 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;

long long 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;

mt19937 rng(14978141);

int rnd(int l, int r) {
  return l + rng() % (r - l + 1);
}

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];
        long long tmp = 1LL * can_win[j][k - 1][nxt] - gain[j][k - 1][i];
        if (can_win[j][k - 1][nxt] == 1e9) tmp = 1e9;
        tmp = max(tmp, 0LL);
        can_win[j][k][i] = min(can_win[j][k - 1][i], (int) tmp);
      }
    }
  }

//  cout << go[8][0][100] << " " << can_win[8][M][100] << endl;

	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 (can_win[j][k][x] != 1e9 && 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;
  }

//  int n = 4e5, q = 5e4;
//
//  vector<int> s(n), p(n), w(n), l(n);
//
//  for(int i = 0; i < n; i++) s[i] = 1e7;
//  for(int i = 0; i < n; i++) p[i] = 1;
//  for(int i = 0; i < n; i++) w[i] = i + 1;
//  for(int i = 0; i < n; i++) l[i] = 0;
//
//  init(n, s, p, w, l);
//
//
//  while (q--) {
//    int x = rnd(0, n - 1), z = rnd(1, 1e7);
//    cout << simulate(x, z) << endl;
//  }
//  cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
//  return 0;

}
#endif // ngu

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