Submission #609966

#	Time	Username	Problem	Language	Result	Execution time	Memory
609966		Temmie	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	1545 ms	1106128 KiB

dungeons

#include <bits/stdc++.h>

int n;
std::vector <int> s, p, w, l;

struct Index {
	int dest;
	long long plus;
	long long consr;
} bin[25][20][50'005];

void init(int _n, std::vector <int> _s, std::vector <int> _p, std::vector <int> _w, std::vector <int> _l) {
	n = _n;
	s = _s;
	p = _p;
	w = _w;
	l = _l;
	for (int b = 0; b < 25; b++) {
		for (int i = 0; i < n; i++) {
			if (s[i] < (1 << b)) {
				bin[b][0][i] = w[i] == n ? (Index) { -1, 0, 0 } : (Index) { w[i], s[i], 1LL << 60 };
			} else {
				bin[b][0][i] = l[i] == n ? (Index) { -1, 0, 0 } : (Index) { l[i], p[i], s[i] };
			}
		}
	}
	for (int b1 = 0; b1 < 25; b1++) {
		for (int b2 = 1; b2 < 20; b2++) {
			for (int i = 0; i < n; i++) {
				bin[b1][b2][i] = bin[b1][b2 - 1][i].dest == -1 || bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].dest == -1 ? (Index) { -1, 0, 0 } :
				(Index) { bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].dest, bin[b1][b2 - 1][i].plus + bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].plus, std::min(bin[b1][b2 - 1][i].consr, bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].consr - bin[b1][b2 - 1][i].plus) };
			}
		}
	}
}

long long simulate(int x, int z) {
	long long ans = z;
	for (int b1 = 0; x < n; ) {
		while (b1 + 1 < 25 && ans >= (1 << (b1 + 1))) {
			b1++;
		}
		for (int b2 = 19; ~b2; b2--) {
			if (bin[b1][b2][x].dest != -1 && ans < bin[b1][b2][x].consr) {
				ans += bin[b1][b2][x].plus;
				x = bin[b1][b2][x].dest;
			}
		}
		if (ans >= s[x]) {
			ans += s[x];
			x = w[x];
		} else {
			ans += p[x];
			x = l[x];
		}
	}
	return ans;
}

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