Submission #1019198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019198		aykhn	Dungeons Game (IOI21_dungeons)	C++17	24 / 100	7055 ms	135244 KiB

dungeons

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

using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 5e4 + 5;
const int LOG = 30;

int N;
array<long long, 2> dpw[LOG][MXN], dplw[LOG][MXN];
int dplp[LOG][MXN];
long long dep[MXN];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	N = n;
	for (int i = n - 1; i >= 0; i--) dep[i] = dep[w[i]] + s[i];
	for (int i = 0; i < n; i++)
	{
		dpw[0][i] = {w[i], s[i] + dep[i]};
		dplp[0][i] = l[i];
		dplw[0][i] = {p[i], s[i]};
	}
	dpw[0][n] = {n, -inf}, dplp[0][n] = n, dplw[0][n] = {0, -inf};
	for (int lg = 1; lg < LOG; lg++)
	{
		for (int i = 0; i <= n; i++)
		{
			long long pw = dpw[lg - 1][i][0], pl = dplp[lg - 1][i];
			long long ls = dplw[lg - 1][i][0], lm = dplw[lg - 1][pl][1];
			dpw[lg][i] = {dpw[lg - 1][pw][0], max(dpw[lg - 1][i][1], dpw[lg - 1][pw][1])};
			dplp[lg][i] = dplp[lg - 1][pl];
			dplw[lg][i] = {ls + dplw[lg - 1][pl][0], min(dplw[lg - 1][i][1], lm - ls)};
		}
	}
}

long long simulate(int x, int z) 
{
	long long val = z;
	while (1)
	{
		if (x == N) break;
		for (int i = LOG - 1; i >= 0; i--)
		{
			if (dep[x] + val >= dpw[i][x][1]) 
			{
				val += dep[x] - dep[dpw[i][x][0]];
				x = dpw[i][x][0];
			}
		}
		if (x == N) break;
		for (int i = LOG - 1; i >= 0; i--)
		{
			if (val < dplw[i][x][1]) 
			{
				val += dplw[i][x][0];
				x = dplp[i][x];
			}
		}
	}
	return val;
}

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