| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 972933 | NemanjaSo2005 | 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>
#define ll long long
using namespace std;
const int maxn=4e5+5;
const int maxl=25;
const int baza=8;
int N,step[10],potrebno[maxn];
ll dobija[maxn];
int koji[maxn][baza+2][maxl+2];
ll suma[maxn][baza+2][maxl+2],gubit[maxn][baza+2][maxl+2];
vector<int> S,P,W,L;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
S=s;
P=p;
W=w;
L=l;
N=n;
potrebno[N]=1;
dobija[N]=0;
for(int i=N-1;i>=0;i--){
potrebno[i]=max(s[i],potrebno[w[i]]-s[i]);
dobija[i]=dobija[w[i]]+s[i];
}
step[0]=1;
for(int i=1;i<=baza;i++)
step[i]=step[i-1]*baza;
for(int b=0;b<baza;b++){
for(int i=0;i<N;i++)
if(s[i]<=step[b]){
koji[i][b][0]=w[i];
suma[i][b][0]=s[i];
gubit[i][b][0]=1e9;
}
else{
koji[i][b][0]=l[i];
suma[i][b][0]=p[i];
gubit[i][b][0]=s[i];
}
for(int j=1;j<=maxl;j++)
for(int i=1;i<=N;i++){
int sl=koji[i][b][j-1];
koji[i][b][j]=koji[sl][b][j-1];
suma[i][b][j]=suma[i][b][j-1]+suma[sl][b][j-1];
gubit[i][b][j]=min(gubit[i][b][j-1],gubit[sl][b][j-1]-suma[i][b][j-1]);
}
}
}
ll simulate(int poz,int s){
ll snaga=s;
if(potrebno[poz]<=snaga)
return snaga+dobija[poz];
int b=baza-1;
while(step[b]>snaga)
b--;
for(int i=maxl;i>=0;i--)
if(gubit[poz][b][i]>snaga){
snaga+=suma[poz][b][i];
poz=koji[poz][b][i];
}
for(int it=1;it<=5;it++){
if(poz==N)
break;
if(snaga>=S[poz]){
snaga+=S[poz];
poz=W[poz];
}
else{
snaga+=P[poz];
poz=L[poz];
}
}
if(potrebno[poz]<=snaga)
return snaga+dobija[poz];
return simulate(poz,snaga);
}