| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 826197 | TheSahib | 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 ll long long
#define pii pair<int, ll>
const ll oo = 1e9 + 9;
const int MAX = 500005;
const int LOGMAX = 24;
const int startLog = 12;
int n;
vector<int> S, W, P, L;
struct G{
array<ll, 3> par[LOGMAX + 1][MAX];
void preCalc(){
for (int j = 1; j <= LOGMAX; j++)
{
for (int i = 0; i <= n; i++)
{
int m = par[j - 1][i][0];
par[j][i][0] = par[j - 1][m][0];
par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
par[j][i][2] = max(par[j - 1][i][2], par[j - 1][m][2] + par[j - 1][i][1]);
}
}
}
pii lift(ll start, ll target, int v){
if(start >= target || v == n) return {v, start};
for(int j = LOGMAX; j >= 0 && v != n; --j){
ll a = start + par[j][v][1];
if(a < target && (start + par[j][v][2] < 0)){
start = a;
v = par[j][v][0];
}
}
if(v == n){
return {n, start};
}
if(start >= S[v]){
start += S[v];
v = W[v];
}
else{
start += P[v];
v = L[v];
}
return {v, start};
}
};
vector<ll> v;
G gs[LOGMAX - startLog + 1];
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;
for(int i = startLog; i < LOGMAX; ++i){
v.push_back((1 << i));
}
for (int i = 0; i < v.size(); i++)
{
for(int j = 0; j <= N; ++j){
if(j == N){
gs[i].par[0][j] = {N, 0, -oo * oo};
continue;
}
if(s[j] > v[i]){
gs[i].par[0][j] = {l[j], p[j], p[j] - s[j]};
}
else{
gs[i].par[0][j] = {w[j], s[j], -oo * oo};
}
}
gs[i].preCalc();
}
v.push_back(oo * oo);
return;
}
ll simulate(int x, int z) {
ll u = x;
ll s = z;
while(s < (1 << startLog) && u != n){
if(s >= S[u]){
s += S[u];
u = W[u];
}
else{
s += P[u];
u = L[u];
}
}
for (int i = 0; i < v.size() - 1; i++)
{
while(s < v[i + 1] && u != n){
pii p = gs[i].lift(s, v[i + 1], u);
u = p.first;
s = p.second;
}
}
return s;
}