Submission #797971

#	Time	Username	Problem	Language	Result	Execution time	Memory
797971		iee	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4635 ms	1790320 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int Base = 8, LN = 25, LS = 9, N = 4e5 + 5;
using ll = long long;
constexpr ll inf = 1e18;
int n;
int go[LS][N][LN];
ll lim[LS][N][LN], gain[LS][N][LN], pw[LS];
vector<int> s, p, win, lose;
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, win = W, lose = L;
	for (int i = pw[0] = 1; i < LS; i++) {
		pw[i] = pw[i - 1] * Base;
	}
	for (int C = 0; C < LS; C++) {
		for (int i = 0; i < n; i++) {
			if (pw[C] >= s[i]) {
				if (win[i] == n) {
					go[C][i][0] = -1;
				} else {
					go[C][i][0] = win[i];
					gain[C][i][0] = s[i];
					lim[C][i][0] = inf;
				}
			} else {
				if (lose[i] == n) {
					go[C][i][0] = -1;
				} else {
					go[C][i][0] = lose[i];
					gain[C][i][0] = p[i];
					lim[C][i][0] = s[i];
				}
			}
		}
	}
	for (int C = 0; C < LS; C++) {
		for (int j = 1; j < LN; j++) {
			for (int i = 0; i < n; i++) {
				if (go[C][i][j - 1] == -1 || go[C][go[C][i][j - 1]][j - 1] == -1) {
					go[C][i][j] = -1;
					continue;
				}
				go[C][i][j] = go[C][go[C][i][j - 1]][j - 1];
				gain[C][i][j] = gain[C][i][j - 1] + gain[C][go[C][i][j - 1]][j - 1];
				lim[C][i][j] = min(lim[C][i][j - 1], lim[C][go[C][i][j - 1]][j - 1] - gain[C][i][j - 1]);
			}
		}
	}
}

long long simulate(int x, int z) {
	long long str = z, c = 0;
	while (x != n) {
		while (c + 1 < LS && pw[c + 1] <= str) c++;
		for (int i = LN - 1; i >= 0; i--) {
			if (go[c][x][i] == -1) continue;
			if (str < lim[c][x][i]) {
				str += gain[c][x][i];
				x = go[c][x][i];
			}
		}
		if (str >= s[x]) str += s[x], x = win[x];
		else str += p[x], x = lose[x];
	}
	return str;
}

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