| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1074706 | vnm06 | 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;
int N;
vector<int> S, P, W, L;
int vert[10][400005][10];
long long jmp[10][400005][10];
long long gran[10][400005][10];
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 le=1, ri=5;
for(int tree=0; tree<10; tree++)
{
for(int i=0; i<n; i++)
{
if(s[i]<le)
{
vert[tree][i][0]=w[i];
jmp[tree][i][0]=s[i];
gran[tree][i][0]=ri;
}
else if(s[i]>ri)
{
vert[tree][i][0]=l[i];
jmp[tree][i][0]=p[i];
gran[tree][i][0]=ri;
}
else
{
vert[tree][i][0]=l[i];
jmp[tree][i][0]=p[i];
gran[tree][i][0]=s[i]-1;
}
}
for(int lvl=1; lvl<10; lvl++)
{
for(int i=0; i<n; i++)
{
vert[tree][i][lvl]=vert[tree][i][lvl-1];
jmp[tree][i][lvl]=jmp[tree][i][lvl-1];
gran[tree][i][lvl]=gran[tree][i][lvl-1];
for(int j=1; j<=5; j++)
{
int nv=vert[tree][i][lvl];
if(nv==n) break;
vert[tree][i][lvl]=vert[tree][nv][lvl-1];
gran[tree][i][lvl]=min(gran[tree][i][lvl], max(0, gran[tree][nv][lvl-1]-jmp[tree][i][lvl]));
if(gran[tree][i][lvl]<=0) break;
jmp[tree][i][lvl]+=jmp[tree][nv][lvl-1];
}
}
}
le*=6;
ri=le*6-1;
}
return;
}
long long simulate(int x, int z) {
int v=x;
long long st=z;
int tree=0, le=1, ri=5;
while(v!=N)
{
while(tree<9 && st>ri)
{
le*=6;
ri=le*6-1;
tree++;
}
for(int lvl=9; lvl>=0; lvl--)
{
for(int j=5;; j--)
{
if(st<=gran[tree][v][lvl])
{
st+=jmp[tree][v][lvl];
v=vert[tree][v][lvl];
if(v==N) break;
}
else break;
}
if(v==N) break;
}
if(v==N) break;
if(st<S[v])
{
st+=P[v];
v=L[v];
}
else
{
st+=S[v];
v=W[v];
}
}
return st;
}