| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209075 | 7ak | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int LOG3 = 25;
const int BASE = 2;
const int LOG2 = 25;
const int N = (int)4e5;
const ll inf = (ll)1e18;
ll gain[LOG3][LOG2][N];
ll lim[LOG3][LOG2][N];
int go[LOG3][LOG2][N];
vector<int> S, P, W, L;
ll B[LOG3];
int n;
void init(int _n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
n = _n;
B[0] = 1;
for(int i = 1; i < LOG3; i ++ ){
B[i] = B[i - 1] * BASE;
}
S = s;
P = p;
W = w;
L = l;
for(int C = 0; C < LOG3; C ++ ){
for(int i = 0 ; i < n; i ++ ){
if(S[i] < B[C]){
if(w[i] == n){
go[C][0][i] = -1;
}
else{
go[C][0][i] = w[i];
gain[C][0][i] = S[i];
lim[C][0][i] = inf;
}
}
else{
if(l[i] == n){
go[C][0][i] = -1;
}
else{
go[C][0][i] = l[i];
gain[C][0][i] = p[i];
lim[C][0][i] = S[i];
}
}
}
}
for(int C = 0 ; C < LOG3; C ++ ){
for(int lg = 1; lg < LOG2; lg ++ ){
for(int i = 0 ; i < n; i ++ ){
if(go[C][lg-1][i] == -1 || go[C][lg-1][go[C][lg-1][i]] == -1){
go[C][lg][i] = -1;
}
else{
go[C][lg][i] = go[C][lg-1][go[C][lg-1][i]];
gain[C][lg][i] = gain[C][lg-1][i] + gain[C][lg-1][go[C][lg-1][i]];
lim[C][lg][i] = min(lim[C][lg-1][i], lim[C][lg-1][go[C][lg-1][i]] - gain[C][lg-1][i]);
}
}
}
}
return;
}
ll simulate(int x, int Z) {
ll strength = Z;
int curb = 0;
while(x != n){
while(curb + 1 < LOG3 && B[curb + 1] <= strength){
curb ++ ;
}
for(int lg = LOG2 - 1; lg >= 0 ; lg -- ){
if(go[curb][lg][x] == -1) continue;
if(strength >= lim[curb][lg][x]) continue;
strength += gain[curb][lg][x];
x = go[curb][lg][x];
}
if(strength >= S[x]){
strength += S[x];
x = W[x];
}
else{
strength += P[x];
x = L[x];
}
// one "special" manual move
}
return strength;
}