Submission #1250531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250531		Joon_Yorigami	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	3564 ms	1438564 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 maxphase = 10;
constexpr ll loge = 30;
constexpr int inf = 1e9;

pair<int, pair<int, int>> jump[maxphase][maxn][loge];
ll n;
vll l;
vll p;
vll s;
vll w;
vll pow2;
vll rem(maxn,0);

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);
  l.push_back(n);
  w.push_back(n);
  p.push_back(0);
  s.push_back(0);
  for(int i=0;i<maxphase;i++)
    pow2.push_back(1ll<<i*3);
  for(int t=0;t<maxphase;t++)
  {
		for(int i=0;i<n;i++)
    {
			if(t>0&&S[i]<=pow2[t-1])
      {
				jump[t][i][0].first=w[i];
				jump[t][i][0].second={s[i],-inf};
			}
			else
      {
				jump[t][i][0].first=l[i];
				jump[t][i][0].second={p[i],-s[i]};
			}
		}
  }
  for(int t=0;t<maxphase;t++)
  {
    for(int k=1;k<loge;k++)
    {
      jump[t][N][k].first=N;
			jump[t][N][k].second={0,-inf};
		  for(int i=0;i<n;i++)
      {
        int nxt=jump[t][i][k-1].first;
				jump[t][i][k].first=jump[t][nxt][k-1].first;
				jump[t][i][k].second={min(inf,jump[t][i][k-1].second.first+jump[t][nxt][k-1].second.first),max(jump[t][i][k-1].second.second,jump[t][i][k-1].second.first+jump[t][nxt][k-1].second.second)};
      }
    }
  }
  rem[n]=0;
  for(int i=n-1;i>=0;i--)
    rem[i]=rem[w[i]]+s[i];
}

long long simulate(int x, int owo) {
	ll strength=owo;
	int t=0;
	while(x!=n)
  {
		while(t<maxphase&&pow2[t]<= strength)
			t++;
		if(t==maxphase)
			break;
		ll sum=0;
		for(int k=loge-1;k>=0;k--)
    {
			if(sum+jump[t][x][k].second.first<inf&&strength+jump[t][x][k].second.second<0)
      {
				strength+=jump[t][x][k].second.first;
				sum+=jump[t][x][k].second.first;
				x=jump[t][x][k].first;
			}
		}
		if(strength>=s[x])
    {
			strength+=s[x];
			x=w[x];
		}
		else
    {
			strength+=p[x];
			x=l[x];
		}
	}
	return strength+rem[x];
}

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