| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 599472 | definitelynotmee | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>;
const int T = 10000;
struct jmp{
ll to, plus, win;
jmp merge(jmp b){
jmp ret;
ret.to = b.to;
ret.plus = plus+b.plus;
ret.win = min(win,b.win-plus);
return ret;
}
};
jmp lift[15][24][400000];
vector<ll> windp;
int N;
vector<int> 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 =s;
P = p;
W = w;
L = l;
int t = T;
for(int x = 0; x < 15; x++){
for(int i = 0; i < n; i++){
if(s[i] <= t){
lift[x][0][i] = {w[i],s[i],1ll<<60};
if(w[i] == n){
lift[x][0][i].win = 0, lift[x][0][i].to = i;
}
} else {lift[x][0][i] = {l[i],p[i],s[i]};
if(l[i] == n)
lift[x][0][i].win = 0, lift[x][0][i].to = i;
}
}
for(int i = 1; i < 24; i++){
for(int j = 0; j < n; j++)
lift[x][i][j] = lift[x][i-1][j].merge(lift[x][i-1][lift[x][i-1][j].to]);
}
t*=2;
}
windp = vector<ll>(n+1);
for(int i = n-1; i >= 0; i--)
windp[i] = windp[w[i]]+s[i];
return;
}
long long simulate(int x, int Z) {
ll z = Z;
int it = T;
while(it-- && x != N){
if(S[x] <= z){
z+=S[x];
x=W[x];
} else {
z+=P[x];
x=L[x];
}
}
int power = 0;
while(x!=N && z < int(1e7)){
while(z >= T*(1<<power+1) && power < 14)
power++;
for(int i = 23; i>= 0; i--){
if(lift[power][i][x].win > z){
z+=lift[power][i][x].plus;
x = lift[power][i][x].to;
}
}
if(S[x] <= z){
z+=S[x];
x=W[x];
} else {
z+=P[x];
x=L[x];
}
}
return z+windp[x];
}