| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 538814 | MilosMilutinovic | 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
const int N=400050;
const int L=25;
const int K=10;
const ll inf=(ll)1e18;
int n,nxt[N][L][L],S[N],W[N];
ll pw[K+5],sum[N][L][K],mn[N][L][K],ft[N];
vector<pair<int,int>> E[N];
void DFS(int u,ll tot){
ft[u]=tot;
for(auto e:E[u])DFS(e.first,tot+e.second);
}
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
::n=n;for(int i=0;i<n;i++)S[i]=s[i],W[i]=w[i];W[n]=n;S[n]=0;
pw[0]=1;for(int i=1;i<=K;i++)pw[i]=pw[i-1]*8;
for(int i=0;i<K;i++){
int h=pw[i];
nxt[n][0][i]=n;
sum[n][0][i]=0;
mn[n][0][i]=inf;
for(int j=0;j<n;j++){
if(s[j]<=h){
nxt[j][0][i]=w[j];
sum[j][0][i]=s[j];
mn[j][0][i]=inf;
}else{
nxt[j][0][i]=l[j];
sum[j][0][i]=p[j];
mn[j][0][i]=s[j];
}
}
for(int j=1;j<L;j++)for(int l=0;l<=n;l++){
nxt[l][j][i]=nxt[nxt[l][j-1][i]][j-1][i];
sum[l][j][i]=min(inf,sum[l][j-1][i]+sum[nxt[l][j-1][i]][j-1][i]);
mn[l][j][i]=min(mn[l][j-1][i],mn[nxt[l][j-1][i]][j-1][i]-sum[l][j-1][i]);
}
}
for(int i=0;i<n;i++)E[w[i]].push_back({i,s[i]});
DFS(n,0);
}
ll simulate(int x,int z){
ll h=z;
for(int i=0;i<K;i++){
while(1){
if(h>=pw[i+1]||x==n)break;
for(int j=L-1;j>=0;j--){
if(mn[x][j][i]>h){
h+=sum[x][j][i];
x=nxt[x][j][i];
}
}
h+=S[x];x=W[x];
}
}
return h+ft[x];
}