Submission #1048593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048593		parsadox2	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2655 ms	164888 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10 , Sq = 1000 , B = N / Sq + 2 , inf = 1e7 , Lg = 16;

int n , nex[N] , pos[N][Lg];
long long dis[N] , val[N] , sum[N][Lg] , best[N][Lg];
vector <int> s , p , w , l;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n = nn;
	s = ss;
	p = pp;
	w = ww;
	l = ll;
	dis[n] = 0;
	nex[n] = n;
	l.push_back(n);
	w.push_back(n);
	p.push_back(0);
	s.push_back(0);
	for(int i = n - 1 ; i >= 0 ; i--)
	{
		dis[i] = dis[w[i]] + s[i];
		if(s[i] >= Sq)
		{
			nex[i] = i;
			val[i] = 0;
		}
		else
		{
			nex[i] = nex[w[i]];
			val[i] = s[i] + val[w[i]];
		}
	}
	for(int i = 0 ; i <= n ; i++)
	{
		sum[i][0] = p[i] + val[l[i]];
		pos[i][0] = nex[l[i]];
		best[i][0] = s[pos[i][0]] - sum[i][0];
	}
	for(int j = 1 ; j < Lg ; j++)
	{
		for(int i = 0 ; i <= n ; i++)
		{
			sum[i][j] = sum[i][j - 1] + sum[pos[i][j - 1]][j - 1];
			pos[i][j] = pos[pos[i][j - 1]][j - 1];
			best[i][j] = min(best[i][j - 1] , best[pos[i][j - 1]][j - 1] - sum[i][j]);
		}
	}
	return;
}

long long simulate(int x, int zz) {
	long long z = zz;
	while(z < Sq && x != n)
	{
		if(z >= s[x])
		{
			z += s[x];
			x = w[x];
		}
		else
		{
			z += p[x];
			x = l[x];
		}
	}
	if(x == n)
		return z;
	while(z < inf)
	{
		z += val[x];
		x = nex[x];
		if(x == n)
			break;
		if(z >= s[x])
		{
			z += s[x];
			x = w[x];
		}
		else
		{
			for(int i = Lg - 1 ; i >= 0 ; i--)
			{
				if(best[x][i] > z)
				{
					z += sum[x][i];
					x = pos[x][i];
				}
			}
			z += p[x];
			x = l[x];
		}
	}
	z += dis[x];
	return z;
}

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