Submission #990959

#	Time	Username	Problem	Language	Result	Execution time	Memory
990959		AdamGS	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4757 ms	1877344 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=4e5+7, LG=24, LG2=15, INF=1e9+7;
int nxt[LIM][LG2][LG], sum[LIM][LG2][LG], ile[LIM][LG2][LG], pot[LG2+1];
ll nxt2[LIM][LG], sum2[LIM][LG], S[LIM], P[LIM], W[LIM], L[LIM], n;
void init(int _n, vector<int>_s, vector<int>_p, vector<int>_w, vector<int>_l) {
  pot[0]=1;
  rep(i, LG2) pot[i+1]=pot[i]*3;
  n=_n;
  rep(i, n) {
    S[i]=_s[i];
    P[i]=_p[i];
    W[i]=_w[i];
    L[i]=_l[i];
  }
  rep(i, LG2) {
    nxt[n][i][0]=n;
    rep(j, n) {
      if(S[j]>=pot[i]) {
        nxt[j][i][0]=L[j];
        sum[j][i][0]=P[j];
        ile[j][i][0]=min(S[j], pot[i+1]-P[j]);
      } else {
        nxt[j][i][0]=W[j];
        sum[j][i][0]=S[j];
        ile[j][i][0]=pot[i+1]-S[j];
      }
    }
    for(int l=1; l<LG; ++l) {
      rep(j, n+1) {
        nxt[j][i][l]=nxt[nxt[j][i][l-1]][i][l-1];
        sum[j][i][l]=sum[j][i][l-1]+sum[nxt[j][i][l-1]][i][l-1];
        ile[j][i][l]=min(ile[j][i][l-1], ile[nxt[j][i][l-1]][i][l-1]-sum[j][i][l-1]);
        sum[j][i][l]=min(sum[j][i][l], INF);
        ile[j][i][l]=max(ile[j][i][l], 0);
      }
    }
  }
  nxt2[n][0]=n;
  rep(i, n) {
    nxt2[i][0]=W[i];
    sum2[i][0]=S[i];
  }
  for(int j=1; j<LG; ++j) {
    rep(i, n+1) {
      nxt2[i][j]=nxt2[nxt2[i][j-1]][j-1];
      sum2[i][j]=sum2[nxt2[i][j-1]][j-1]+sum2[i][j-1];
    }
  }
  return;
}
ll simulate(int x, int _z) {
  ll z=_z;
  int i=0;
  while(true) {
    while(i<LG2 && pot[i+1]<=z) ++i;
    if(i==LG2) break;
    for(int j=LG-1; j>=0; --j) if(nxt[x][i][j]<n && ile[x][i][j]>z) {
      z+=sum[x][i][j];
      x=nxt[x][i][j];
    }
    if(z>=S[x]) {
      z+=S[x];
      x=W[x];
    } else {
      z+=P[x];
      x=L[x];
    }
    if(x==n) return z;
  }
  for(int i=LG-1; i>=0; --i) if(nxt2[x][i]<n) {
    z+=sum2[x][i];
    x=nxt2[x][i];
  }
  z+=sum2[x][0];
  x=nxt2[x][0];
  return z;
}

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