Submission #972943

#	Time	Username	Problem	Language	Result	Execution time	Memory
972943		NemanjaSo2005	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6196 ms	1304492 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=4e5+5;
const int maxl=25;
const int baza=8;
int N,step[10],potrebno[maxn];
ll dobija[maxn];
int koji[maxn][baza+2][maxl+2],gubit[maxn][baza+2][maxl+2];
int suma[maxn][baza+2][maxl+2];
vector<int> S,P,W,L;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
   S=s;
   P=p;
   W=w;
   L=l;

   N=n;
   potrebno[N]=1;
   dobija[N]=0;
   for(int i=N-1;i>=0;i--){
      potrebno[i]=max(s[i],potrebno[w[i]]-s[i]);
      dobija[i]=dobija[w[i]]+s[i];
   }

   step[0]=1;
   for(int i=1;i<=baza;i++)
      step[i]=step[i-1]*baza;
   for(int b=0;b<baza;b++){
      for(int i=0;i<N;i++)
         if(s[i]<=step[b]){
            koji[i][b][0]=w[i];
            suma[i][b][0]=s[i];
            gubit[i][b][0]=1e9;
         }
         else{
            koji[i][b][0]=l[i];
            suma[i][b][0]=p[i];
            gubit[i][b][0]=s[i];
         }
      for(int j=1;j<=maxl;j++)
         for(int i=1;i<=N;i++){
            int sl=koji[i][b][j-1];
            koji[i][b][j]=koji[sl][b][j-1];
            suma[i][b][j]=min(suma[i][b][j-1]+suma[sl][b][j-1],1'000'000'000);
            gubit[i][b][j]=min(gubit[i][b][j-1],gubit[sl][b][j-1]-suma[i][b][j-1]);
         }
   }
}

ll simulate(int poz,int s){
   ll snaga=s;
   if(potrebno[poz]<=snaga)
      return snaga+dobija[poz];
   int b=baza-1;
   while(step[b]>snaga)
      b--;
   for(int i=maxl;i>=0;i--)
      if(gubit[poz][b][i]>snaga){
         snaga+=suma[poz][b][i];
         poz=koji[poz][b][i];
      }
   for(int it=1;it<=5;it++){
      if(poz==N)
         break;
      if(snaga>=S[poz]){
         snaga+=S[poz];
         poz=W[poz];
      }
      else{
         snaga+=P[poz];
         poz=L[poz];
      }
   }
   if(potrebno[poz]<=snaga)
      return snaga+dobija[poz];
   return simulate(poz,snaga);
}

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