Submission #1248818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248818		Joon_Yorigami	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	1 ms	840 KiB

dungeons

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

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

//binlift
ll par[maxn][loge];
ll gain[maxn][loge];
ll allwin[maxn];
ll allstrength;
ll N;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
  N=n;
  allstrength=s[0];
  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];
    }
  }
  for(int i=n;i>=0;i--)
  {
    allwin[i]=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 p = 24;
  while(x!=N && p>=0 &&strength<allstrength)
  {
    if((p==0&&strength<allstrength) || (par[x][p]!=N && strength+gain[x][p]<=allstrength))
    {
      strength+=gain[x][p];
      x=par[x][p];
    }
    p--;
  }
	return strength+allwin[x];
}

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