| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 775256 | SanguineChameleon | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
const int maxN = 5e4 + 20;
const int maxT = 25;
const int maxK = 30;
pair<int, pair<long long, long long>> jump[maxT][maxN][maxK];
int S[maxN];
int P[maxN];
int W[maxN];
int L[maxN];
vector<int> times;
int N, T;
void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, 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];
}
W[N] = N;
for (int i = 0; i < 24; i++) {
times.push_back(1 << i);
}
sort(times.begin(), times.end());
T = times.size();
for (int t = 0; t <= T; t++) {
for (int i = 0; i < N; i++) {
if (t > 0 && S[i] <= times[t - 1]) {
jump[t][i][0].first = W[i];
jump[t][i][0].second.first = S[i];
jump[t][i][0].second.second = -inf;
}
else {
jump[t][i][0].first = L[i];
jump[t][i][0].second.first = P[i];
jump[t][i][0].second.second = -S[i];
}
}
jump[t][N][0].first = N;
jump[t][N][0].second.first = 0;
jump[t][N][0].second.second = -inf;
for (int k = 1; k < maxK; k++) {
jump[t][N][k].first = N;
jump[t][N][k].second.first = 0;
jump[t][N][k].second.second = -inf;
for (int i = 0; i < N; i++) {
int nxt = jump[t][i][k - 1].first;
jump[t][i][k].first = jump[t][nxt][k - 1].first;
jump[t][i][k].second.first = jump[t][i][k - 1].second.first + jump[t][nxt][k - 1].second.first
jump[t][i][k].second.second = max(jump[t][i][k - 1].second.second, jump[t][i][k - 1].second.first + jump[t][nxt][k - 1].second.second)));
}
}
}
return;
}
long long simulate(int X, int _Z) {
long long Z = _Z;
int t = 0;
while (X != N) {
while (t < T && times[t] <= Z) {
t++;
}
for (int k = maxK - 1; k >= 0; k--) {
if (Z + jump[t][X][k].second.second < 0) {
Z += jump[t][X][k].second.first;
X = jump[t][X][k].first;
}
}
Z += S[X];
X = W[X];
}
return Z;
}