Submission #1237260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237260		SalihSahin	Dungeons Game (IOI21_dungeons)	C++20	37 / 100	7091 ms	292416 KiB

dungeons

#include "bits/stdc++.h"
#include "dungeons.h"
using namespace std;
#define ll long long

const int inf = 2e9 + 5;
const int N = 1e6 + 5;
const int K = 24;

vector<vector<int> > nxt, add, jump;
vector<vector<ll> > sum, mx;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
   nxt.resize(n+1);
   add.resize(n+1);
   for(int i = 0; i < n; i++){
      nxt[i].resize(2);
      nxt[i][0] = l[i];
      nxt[i][1] = w[i];

      add[i].resize(2);
      add[i][0] = p[i];
      add[i][1] = s[i];
   }
   nxt[n].resize(2);
   add[n].resize(2);
   nxt[n][0] = nxt[n][1] = n;
   add[n][0] = add[n][1] = 0;

   jump.resize(n+1);
   sum.resize(n+1);
   mx.resize(n+1);
   for(int i = 0; i <= n; i++){
      jump[i].resize(K);
      sum[i].resize(K);
      mx[i].resize(K);
      jump[i][0] = nxt[i][1];
      sum[i][0] = add[i][1];
      mx[i][0] = add[i][1];
   }

   for(int i = 1; i < K; i++){
      for(int j = 0; j <= n; j++){
         jump[j][i] = jump[jump[j][i-1]][i-1];
         sum[j][i] = sum[j][i-1] + sum[jump[j][i-1]][i-1];
         mx[j][i] = max(mx[j][i-1], mx[jump[j][i-1]][i-1] - sum[j][i-1]);
      }
   }

   return;
}

long long simulate(int x, int z){
   int n = nxt.size() - 1;
   long long cur = z;

   while(x != n){
      for(int j = K-1; j >= 0; j--){
         if(mx[x][j] <= cur){
            cur += sum[x][j];
            x = jump[x][j];
         }
      }

      if(add[x][1] > cur){
         cur += add[x][0];
         x = nxt[x][0];
      }
   }

   return cur;
}

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