| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 542872 | alextodoran | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 50000;
const int N_QITS = 10;
const int S_BITS = 25;
int N;
int strength[N_MAX];
int winBonus[N_MAX];
int loseBonus[N_MAX];
int winEdge[N_MAX];
int loseEdge[N_MAX];
struct Jump {
int last;
ll bonus;
ll maxDiff;
// maximum (bonus - strength) at some moment when we lost
};
Jump operator + (const Jump &j1, const Jump &j2) {
return Jump{j2.last, j1.bonus + j2.bonus, max(j1.maxDiff, j1.bonus + j2.maxDiff)};
}
Jump jump[N_MAX + 1][S_BITS][N_QITS];
void init (int _N, int _S[], int _P[], int _W[], int _L[]) {
// Transfer input to global
N = _N;
for (int u = 0; u < N; u++) {
strength[u] = _S[u];
winBonus[u] = _S[u];
loseBonus[u] = _P[u];
winEdge[u] = _W[u];
loseEdge[u] = _L[u];
}
// Precompute jumps
for (int sbit = 0; sbit < S_BITS; sbit++) {
for (int nqit = 0; nqit < N_QITS; nqit++) {
jump[N][sbit][nqit] = Jump{N, 0, 0};
}
}
for (int u = 0; u < N; u++) {
for (int sbit = 0; sbit < S_BITS; sbit++) {
if ((1 << sbit) > strength[u]) {
jump[u][sbit][0] = Jump{winEdge[u], winBonus[u], LLONG_MIN};
} else {
jump[u][sbit][0] = Jump{loseEdge[u], loseBonus[u], 0 - strength[u]};
}
}
}
for (int nqit = 1; nqit < N_QITS; nqit++) {
for (int u = 0; u < N; u++) {
for (int sbit = 0; sbit < S_BITS; sbit++) {
Jump j = jump[u][sbit][nqit - 1];
j = j + jump[j.last][sbit][nqit - 1];
j = j + jump[j.last][sbit][nqit - 1];
j = j + jump[j.last][sbit][nqit - 1];
jump[u][sbit][nqit] = j;
}
}
}
}
ll simulate (int u, ll currStrength) {
while (true) {
for (int nqit = N_QITS - 1; nqit >= 0; nqit--) {
int sbit = (currStrength <= INT_MAX ? 32 - __builtin_clz(currStrength) : S_BITS);
Jump j = jump[u][sbit][nqit];
while (u < N && currStrength + j.maxDiff < 0) {
u = j.last;
currStrength += j.bonus;
j = jump[u][sbit][nqit];
}
}
if (u == N) {
break;
}
currStrength += winBonus[u];
u = winEdge[u];
}
return currStrength;
}