| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072124 | Ahmed57 | 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 "bits/stdc++.h"
using namespace std;
int BL = 80000;
array<long long,3> P[50001][130][16];
long long inf = 1e18 , N;
vector<int> S , PP , W , L;
void init(int n, vector<int> s, vector<int> p, vector<int> w,vector<int> l){
S = s , PP = p;W = w; L = l;
int cnt = 0;N = n;
for(int cst = 0;cst<=1e7;cst+=BL){
for(int i = 0;i<n;i++){
if(s[i]>=cst){
P[i][cnt][0] = {w[i],s[i],-inf};
}else{
P[i][cnt][0] = {l[i],p[i],s[i]};
}
}
P[n][cnt][0] = {n,0,inf};
for(int j = 1;j<16;j++){
for(int i = 0;i<=n;i++){
P[i][cnt][j][0] = P[P[i][cnt][j-1][0]][cnt][j-1][0];
P[i][cnt][j][1] = P[i][cnt][j-1][1]+P[P[i][cnt][j-1][0]][cnt][j-1][1];
P[i][cnt][j][2] = max(P[i][cnt][j-1][2],P[P[i][cnt][j-1][0]][cnt][j-1][2]-P[i][cnt][j-1][1]);
}
}
cnt++;
}
}
long long simulate(int x, int z) {
long long sum = z;
while(x!=N){
int nah = sum/BL;
for(int i = 15;i>=0;i--){
if(P[x][nah][i][2]>=1e15||(P[x][nah][i][2]<=sum&&P[x][nah][i][2]>=-inf)){
}else{
sum+=P[x][nah][i][1];
x = P[x][nah][i][0];
}
}
if(x==N)break;
if(sum>=S[x]){
sum+=S[x];
x = W[x];
}else{
sum+=PP[x];
x = L[x];
}
}
return sum;
}