Submission #591527

#	Time	Username	Problem	Language	Result	Execution time	Memory
591527		rainboy	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3245 ms	436808 KiB

dungeons

/* https://codeforces.com/blog/entry/74847 */
#include "dungeons.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 400000, L = 25;	/* L = ceil(log2(10^7 + N)) + 1 */
const int INF = 0x3f3f3f3f;
const long long LINF = 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][N + 1], upper[L][N + 1]; long long dd[L][N + 1];
int hh[L][N + 1], jj_[L][N + 1], upper_[L][N + 1]; long long dd_[L][N + 1];

void dfs(int *jj, long long *dd, int *upper, int *hh, int *jj_, long long *dd_, int *upper_, int i) {
	int j, k;

	j = jj[i];
	hh[i] = -1;
	if (hh[j] == -1) {
		hh[i] = 1, jj_[i] = -1;
		j = i, dd_[i] = 0, upper_[i] = INF;
		do {
			upper_[i] = max(min(upper_[i], upper[j] == INF ? INF : upper[j] - dd_[i]), 0);
			dd_[i] += dd[j];
		} while ((j = jj[j]) != i);
	} else {
		if (!hh[j])
			dfs(jj, dd, upper, hh, jj_, dd_, upper_, j);
		hh[i] = 2, jj_[i] = j, dd_[i] = dd[i], upper_[i] = upper[i];
		if (hh[j] != 1 && hh[j] == hh[k = jj_[j]]) {
			hh[i] = hh[j] + 1;
			jj_[i] = jj_[k];
			dd_[i] += dd_[j] + dd_[k];
			upper_[i] = max(min(upper_[i], upper_[j] == INF ? INF : upper_[j] - dd_[i]), 0);
			upper_[i] = max(min(upper_[i], upper_[k] == INF ? INF : upper_[k] - dd_[i] - dd_[j]), 0);
		}
	}
}

void init(int n_, vi ss_, vi pp_, vi jjw_, vi jjl_) {
	int l, 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 (l = 0; l < L; l++) {
		for (i = 0; i <= n; i++)
			if (i == n)
				jj[l][i] = n, dd[l][i] = 0, upper[l][i] = 0;
			else if (ss[i] < 1 << l)
				jj[l][i] = jjw[i], dd[l][i] = ss[i], upper[l][i] = INF;
			else
				jj[l][i] = jjl[i], dd[l][i] = pp[i], upper[l][i] = ss[i];
		for (i = 0; i <= n; i++)
			if (!hh[l][i])
				dfs(jj[l], dd[l], upper[l], hh[l], jj_[l], dd_[l], upper_[l], i);
	}
}

long long simulate(int i, int s_) {
	int l;
	long long s;

	s = s_;
	for (l = 0; l < L && i < n; l++) {
		while (hh[l][i] != 1)
			if (upper_[l][i] == INF || s < upper_[l][i])
				s += dd_[l][i], i = jj_[l][i];
			else if (upper[l][i] == INF || s < upper[l][i])
				s += dd[l][i], i = jj[l][i];
			else
				break;
		if (hh[l][i] == 1) {
			if (s < upper_[l][i])
				s += (upper_[l][i] - s + dd_[l][i] - 1) / dd_[l][i] * dd_[l][i];
			if (upper[l][i] == INF || s < upper[l][i]) {
				s += dd[l][i], i = jj[l][i], l--;
				continue;
			}
		}
		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