| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 960779 | Warinchai | 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 lift[26][20][400005];
long long mn[26][20][400005];
long long dis[26][20][400005];
long long inf=1e18+7;
int N;
vector<int>W;
vector<int>S;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
N=n;
S=s;
W=w;
for(int i=1;i<=25;i++){
int st=(1<<(i-1));
int en=(1<<i)-1;
for(int j=0;j<n;j++){
if(s[j]>en)lift[i][0][j]=l[j],mn[i][0][j]=inf,dis[i][0][j]=p[j];
else if(s[j]>=st)lift[i][0][j]=l[j],mn[i][0][j]=s[j],dis[i][0][j]=p[j];
else lift[i][0][j]=w[j],mn[i][0][j]=inf,dis[i][0][j]=s[j];
}
lift[i][0][n]=n;
mn[i][0][n]=0;
for(int j=1;j<=19;j++){
for(int k=0;k<n;k++){
lift[i][j][k]=lift[i][j-1][lift[i][j-1][k]];
dis[i][j][k]=dis[i][j-1][k]+dis[i][j-1][lift[i][j-1][k]];
mn[i][j][k]=min(mn[i][j-1][k],mn[i][j-1][lift[i][j-1][k]]-dis[i][j-1][k]);
}
}
}
return;
}
long long simulate(int x, int z) {
int c=1,lv=0;
long long pow=z;
while(x<(1<<c)){
lv=c;
c++;
}
while(1){
for(int i=25;i>=0;i--){
if(pow<mn[lv][i][x])pow+=dis[lv][i][x],x=lift[lv][i][x];
}
if(x==N)break;
pow+=S[x];
x=W[x];
lv++;
}
return pow;
}