Submission #1248847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248847		Joon_Yorigami	Dungeons Game (IOI21_dungeons)	C++20	13 / 100	99 ms	28224 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 = 30;

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

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
  n=N;
  for(auto num:L)
    l.push_back(num);
  for(auto num:P)
    p.push_back(num);
  for(auto num:S)
    s.push_back(num);
  for(auto num:W)
    w.push_back(num);
  
  par[n][0]=n;
  gain[n][0]=0;
  for(ll i=0;i<n;i++)
  {
    par[i][0]=l[i];
    gain[i][0]=p[i];
  }
  for(ll j=1;j<loge;j++)
  {
    for(ll 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(ll i=n-1;i>=0;i--)
    allwin[i]=s[i]+allwin[w[i]];
	return;
}

long long simulate(int x, int owo)
{
  ll strength=owo;
  ll ptr = loge-1;
  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--;
  }
  //cerr << par[0][0] << '\n';
  while(x!=n)
  {
    if(strength<s[x])
    {
      strength+=p[x];
      x=l[x];
    }
    else
    {
      strength+=allwin[x];
      x=n;
    }
  }
  //cerr << *max_element(allwin,allwin+n) << '\n';
  return strength;
}

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