Submission #609977

#	Time	Username	Problem	Language	Result	Execution time	Memory
609977		Temmie	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4123 ms	1459276 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[8][19][400'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 < 8; b++) {
		for (int i = 0; i < n; i++) {
			if (s[i] < (1 << (b << 3))) {
				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 < 8; b1++) {
		for (int b2 = 1; b2 < 19; 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 < 8 && ans >= (1 << ((b1 + 1) << 3))) {
			b1++;
		}
		for (int b2 = 18; ~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: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11