Submission #1072122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072122		Ahmed57	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	578 ms	664712 KiB

dungeons

#include "bits/stdc++.h"
 
using namespace std;
int BL = 1000;
array<long long,3> P[50001][51][20];
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<=1e4;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<20;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 = 19;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;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11