Submission #467623

#	Time	Username	Problem	Language	Result	Execution time	Memory
467623		rainboy	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5108 ms	1401496 KiB

dungeons

#include "dungeons.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 400000, L1 = 7, L2 = 25;	/* L2 = ceil(log2(10^7 + N)) + 1 */
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

int ss[N + 1], pp[N + 1], jjw[N + 1], jjl[N + 1], n;
int jj[L1][L2][N + 1]; long long dd[L1][L2][N + 1], upper[L1][L2][N + 1];

void init(int n_, vi ss_, vi pp_, vi jjw_, vi jjl_) {
	int l1, l2, i;

	n = n_;
	for (i = 0; i < n; i++)
		ss[i] = ss_[i], pp[i] = pp_[i], jjw[i] = jjw_[i], jjl[i] = jjl_[i];
	for (l1 = 0; l1 < L1; l1++) {
		for (i = 0; i <= n; i++)
			if (i == n)
				jj[l1][0][i] = n, dd[l1][0][i] = 0, upper[l1][0][i] = 0;
			else if (ss[i] < 1 << l1 * 4)
				jj[l1][0][i] = jjw[i], dd[l1][0][i] = ss[i], upper[l1][0][i] = INF;
			else
				jj[l1][0][i] = jjl[i], dd[l1][0][i] = pp[i], upper[l1][0][i] = ss[i];
		for (l2 = 1; l2 < L2; l2++)
			for (i = 0; i <= n; i++) {
				int j = jj[l1][l2 - 1][i];

				jj[l1][l2][i] = jj[l1][l2 - 1][j];
				dd[l1][l2][i] = min(dd[l1][l2 - 1][i] + dd[l1][l2 - 1][j], INF);
				upper[l1][l2][i] = max(min(upper[l1][l2 - 1][i], upper[l1][l2 - 1][j] == INF ? INF : upper[l1][l2 - 1][j] - dd[l1][l2 - 1][i]), 0);
			}
	}
}

long long simulate(int i, int s_) {
	int l1, l2, r;
	long long s;

	s = s_;
	for (l1 = 0; l1 < L1 && i < n; l1++)
		for (r = 0; r < 16 && i < n; r++) {
			for (l2 = L2 - 1; l2 >= 0; l2--)
				if (s < upper[l1][l2][i])
					s += dd[l1][l2][i], i = jj[l1][l2][i];
			if (i < n) {
				if (s >= ss[i])
					s += ss[i], i = jjw[i];
				else
					s += pp[i], i = jjl[i];
			}
		}
	return s;
}

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