Submission #811945

#	Time	Username	Problem	Language	Result	Execution time	Memory
811945		WLZ	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7093 ms	1288128 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

const ll LINF = 1e18;
const int b = 8;
const int max_log = 9;

int n;
vector< vector<vi> > up; // [k][u][i]: 2^i steps from u, strength [2 ^ k, 2 ^ (k + 1))
vector< vector<vll> > gain, to_win;
vi s, p, w, l;

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<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);
  up.assign(max_log + 1, vector<vi>(n + 1, vi(max_log + 1)));
  gain.assign(max_log + 1, vector<vll>(n + 1, vll(max_log + 1)));
  to_win.assign(max_log + 1, vector<vll>(n + 1, vll(max_log + 1)));
  for (int k = 0, pw = 1; k <= max_log; k++, pw *= b) {
    for (int u = 0; u <= n; u++) {
      up[k][u][0] = (s[u] < pw ? w[u] : l[u]);
      gain[k][u][0] = (s[u] < pw ? s[u] : p[u]);
      to_win[k][u][0] = (s[u] < pw * b ? s[u] : LINF);
    }
    for (int i = 1; i <= max_log; i++) {
      for (int u = 0; u <= n; u++) {
        up[k][u][i] = up[k][up[k][u][i - 1]][i - 1];
        gain[k][u][i] = gain[k][u][i - 1] + gain[k][up[k][u][i - 1]][i - 1];
        to_win[k][u][i] = min(to_win[k][u][i - 1], to_win[k][up[k][u][i - 1]][i - 1] - gain[k][u][i - 1]);
      }
    }
  }
}

long long simulate(int x, int z) {
  ll ans = z, pw = 1;
  int k = 0, u = x;
  while (pw * b <= z) pw *= b, k++;
  while (u != n) {
    while (u != n && ans < pw * b) {
      for (int i = max_log; i >= 0; i--) {
        if (ans + gain[k][u][i] <= pw * b && ans < to_win[k][u][i]) {
          ans += gain[k][u][i];
          u = up[k][u][i];
        }
      }
      if (ans < s[u]) ans += p[u], u = l[u];
      else ans += s[u], u = w[u];
    }
    pw *= b;
    k++;
  }
  return ans;
}

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