Submission #1237269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237269		SalihSahin	Dungeons Game (IOI21_dungeons)	C++20	50 / 100	7092 ms	527260 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, jumpw, jumpl;
vector<vector<ll> > sumw, mxw, suml, mnl;

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;

   jumpw.resize(n+1);
   sumw.resize(n+1);
   mxw.resize(n+1);
   for(int i = 0; i <= n; i++){
      jumpw[i].resize(K);
      sumw[i].resize(K);
      mxw[i].resize(K);
      jumpw[i][0] = nxt[i][1];
      sumw[i][0] = add[i][1];
      mxw[i][0] = add[i][1];
   }

   for(int i = 1; i < K; i++){
      for(int j = 0; j <= n; j++){
         jumpw[j][i] = jumpw[jumpw[j][i-1]][i-1];
         sumw[j][i] = sumw[j][i-1] + sumw[jumpw[j][i-1]][i-1];
         mxw[j][i] = max(mxw[j][i-1], mxw[jumpw[j][i-1]][i-1] - sumw[j][i-1]);
      }
   }

   jumpl.resize(n+1);
   suml.resize(n+1);
   mnl.resize(n+1);
   for(int i = 0; i <= n; i++){
      jumpl[i].resize(K);
      suml[i].resize(K);
      mnl[i].resize(K);
      jumpl[i][0] = nxt[i][0];
      suml[i][0] = add[i][0];
      mnl[i][0] = add[i][1];
   }

   for(int i = 1; i < K; i++){
      for(int j = 0; j <= n; j++){
         jumpl[j][i] = jumpl[jumpl[j][i-1]][i-1];
         suml[j][i] = suml[j][i-1] + suml[jumpl[j][i-1]][i-1];
         mnl[j][i] = min(mnl[j][i-1], mnl[jumpl[j][i-1]][i-1] - suml[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(mxw[x][j] <= cur){
            cur += sumw[x][j];
            x = jumpw[x][j];
         }
      }

      for(int j = K-1; j >= 0; j--){
         if(mnl[x][j] > cur){
            cur += suml[x][j];
            x = jumpl[x][j];
         }
      }
   }

   return cur;
}

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