Submission #1248832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248832		Joon_Yorigami	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	50 ms	23364 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vint = vector<int>;

constexpr ll maxn = 400005;
constexpr ll loge = 25;

//binlift
ll par[maxn][loge];
ll gain[maxn][loge];
ll allwin[maxn];
ll n;
vint l;
vint p;
vint s;
vint w;

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
  n=N;
  l=L;
  p=P;
  s=S;
  w=W;
  par[n][0]=n;
  gain[n][0]=0;
  for(int i=0;i<n;i++)
  {
    par[i][0]=l[i];
    gain[i][0]=p[i];
  }
  for(int j=1;j<loge;j++)
  {
    for(int i=0;i<=n;i++)
    {
      par[i][j]=par[par[i][j-1]][j-1];
      gain[i][j]=gain[par[i][j-1]][j-1]+gain[i][j-1];
    }
  }
  allwin[n]=0;
  for(int i=n-1;i>=0;i--)
    allwin[i]=s[i]+allwin[w[i]];
	return;
}

long long simulate(int x, int strength)
{
  ll ptr = 24;
  while(x!=n && ptr>=0 &&strength<s[x])
  {
    if(par[x][ptr]!=n && strength+gain[x][ptr]<s[par[x][ptr]])
    {
      //cerr << ptr << ": " << strength << "," << gain[x][ptr] << '\n';
      strength+=gain[x][ptr];
      x=par[x][ptr];
    }
    ptr--;
  }
  while(x!=n)
  {
    if(strength<s[x])
    {
      strength+=p[x];
      x=l[x];
    }
    else
    {
      strength+=allwin[x];
      x=n;
    }
  }
  return strength;
}

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