Submission #1034843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034843		Boas	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	983 ms	2097152 KiB

dungeons

#include <bits/stdc++.h>
using namespace std;

#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define loop1(x, i) for (int i = 1; i <= x; i++)
#define ALL(x) begin(x), end(x)
#define pb push_back
#define int long long

typedef vector<int> vi;
typedef vector<signed> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#include "dungeons.h"

int N;
vvvi par, dif;
int sCnt = 0;
vi lvls;

void init(signed n, vi32 s, vi32 p, vi32 w, vi32 l)
{
	N = n;
	set<int> levels = {0};
	loop(n, i) levels.insert(s[i]);
	sCnt = levels.size();
	par = dif = vvvi(sCnt, vvi(30, vi(n + 1)));
	lvls = vi(ALL(levels));
	loop(sCnt, j)
	{
		loop(n, i)
		{
			if (s[i] > lvls[j])
			{
				par[j][0][i] = l[i];
				dif[j][0][i] = p[i];
			}
			else
			{
				par[j][0][i] = w[i];
				dif[j][0][i] = s[i];
			}
		}
		dif[j][0][n] = 0;
		par[j][0][n] = n;
	}
	loop(sCnt, j)
	{
		loop1(29, x)
		{
			loop(n + 1, i)
			{
				int half = par[j][x - 1][i];
				par[j][x][i] = par[j][x - 1][half];
				dif[j][x][i] = dif[j][x - 1][i] + dif[j][x - 1][half];
			}
		}
	}
	lvls.pb((int)4e18);
	return;
}

int simulate(signed a, signed b)
{
	int x = a, z = b;
	loop(sCnt, j)
	{
		int s = lvls[j + 1];
		if (z < s)
		{
			rev(30, i)
			{
				if (dif[j][i][x] + z < s && par[j][i][x] != N)
				{
					z += dif[j][i][x];
					x = par[j][i][x];
				}
			}
			z += dif[j][0][x];
			x = par[j][0][x];
			if (x == N)
				return z;
		}
	}
	return z;
}

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