제출 #1022995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022995		NeroZein	던전 (IOI21_dungeons)	C++17	37 / 100	7067 ms	216236 KiB

dungeons

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

const int LOG = 30;
const int N = 4e5 + 5; 

int n;
int mx[LOG][N];
int nxt[LOG][N];
long long d[LOG][N];
vector<int> s, p, w, l;

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
  n = n_;
  s = s_, p = p_, w = w_, l = l_; 
  d[0][n] = mx[0][n] = 0;
  nxt[0][n] = n; 
  for (int i = 0; i < n; ++i) {
    nxt[0][i] = w[i];
    mx[0][i] = d[0][i] = s[i];
  }
  for (int j = 1; j < LOG; ++j) {
    for (int i = 0; i <= n; ++i) {
      nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
      d[j][i] = d[j - 1][i] + d[j - 1][nxt[j - 1][i]];
      mx[j][i] = max(mx[j - 1][i], mx[j - 1][nxt[j - 1][i]]);
    }
  }
  return;
}

long long simulate(int x, int z) {
  long long strength = z; 
  while (x != n) {
    long long tmp = 0;
    for (int j = LOG - 1; j >= 0; --j) {
      if (mx[j][x] <= strength) {
        tmp += d[j][x];
        x = nxt[j][x];
      }
    }
    strength += tmp;
    if (x == n) {
      return strength;
    }
    if (strength >= s[x]) {
      strength += s[x];
      x = w[x];
    } else {
      strength += p[x];
      x = l[x]; 
    }
  }
  return strength;
}

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