제출 #810628

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

int n;
int max_log = 62;
vector<vi> up;
vector<vll> h, mx;
vll 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.assign(S.begin(), S.end());
  p.assign(P.begin(), P.end());
  w.assign(W.begin(), W.end());
  l.assign(L.begin(), L.end());
  s.push_back(LINF); p.push_back(0); w.push_back(n); l.push_back(n);
  up.assign(n + 1, vi(max_log + 1));
  h.assign(n + 1, vll(max_log + 1));
  mx.assign(n + 1, vll(max_log + 1));
  for (int i = 0; i <= n; i++) {
    up[i][0] = w[i];
    h[i][0] = p[i];
    mx[i][0] = s[i];
  }
  for (int j = 1; j <= max_log; j++) {
    for (int i = 0; i <= n; i++) {
      up[i][j] = up[up[i][j - 1]][j - 1];
      h[i][j] = h[i][j - 1] + h[up[i][j - 1]][j - 1];
      mx[i][j] = max(mx[i][j - 1], mx[up[i][j - 1]][j - 1] - h[i][j - 1]);
    }
  }
}

long long simulate(int x, int z) {
  ll ans = z;
  while (x != n) {
    for (int i = max_log; i >= 0; i--) {
      if (ans >= mx[x][i]) {
        ans += h[x][i];
        x = up[x][i];
      }
    }
    if (ans >= s[x]) {
      ans += p[x];
      x = w[x];
    }
    ans += p[x];
    x = l[x];
  }
	return ans;
}

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