Submission #467620

#	Time	Username	Problem	Language	Result	Execution time	Memory
467620		rainboy	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	590 ms	614856 KiB

dungeons

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

using namespace std;

typedef vector<int> vi;

const int N = 50000, L = 25;	/* L = 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[L][L][N + 1]; long long dd[L][L][N + 1], upper[L][L][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 < L; 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)
				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 < L; 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;
	long long s;

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

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