제출 #812047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
812047		WLZ	던전 (IOI21_dungeons)	C++17	11 / 100	7027 ms	913044 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 int MAXN = (int) 2e5;
const int INF = 0x3f3f3f3f;
const ll LINF = 1e18;
const int b = 8;
const int max_log = 9;

int n;
int up[max_log + 2][MAXN + 5][max_log + 1];
ll gain[max_log + 2][MAXN + 5][max_log + 1];
ll to_win[max_log + 2][MAXN + 5][max_log + 1];
//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 + 2, vector<vi>(n + 1, vi(max_log + 1)));
  //gain.assign(max_log + 2, vector<vll>(n + 1, vll(max_log + 1)));
  //to_win.assign(max_log + 2, vector<vll>(n + 1, vll(max_log + 1)));
  ll pw = 1;
  for (int k = 0; k <= max_log + 1; k++, pw *= b) {
    if (k == max_log + 1) pw = (ll) 1e8;
    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] = (pw <= s[u] && 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) {
    for (int t = 0; t < 3; t++) {
      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];
    }
    while (pw * b <= ans && k <= max_log) pw *= b, k++;
    if (k == max_log + 1) pw = LINF;
  }
  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