Submission #618044

#	Time	Username	Problem	Language	Result	Execution time	Memory
618044		Soumya1	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2020 ms	1018460 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 400000;
const int lg2 = 20;
const int lg10 = 8;
const long long inf = 1e9;
int to[lg10][lg2][mxN];
int lim[lg10][lg2][mxN];
long long add[lg10][lg2][mxN];
int pw[lg10];
int n;
vector<int> s, p, w, l;
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	n = _n, s = _s, p = _p, w = _w, l = _l;
	pw[0] = 1;
	for (int i = 1; i < lg10; i++) pw[i] = pw[i - 1] * 10;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < lg10; j++) {
			if (pw[j] >= s[i]) {
				to[j][0][i] = w[i];
				add[j][0][i] = s[i];
				lim[j][0][i] = inf;
			} else {
				to[j][0][i] = l[i];
				add[j][0][i] = p[i];
				lim[j][0][i] = s[i];
			}
		}
	}
	for (int i = 0; i < lg10; i++) {
		for (int j = 1; j < lg2; j++) {
			for (int k = 0; k < n; k++) {
				if (to[i][j - 1][k] == n) {
					to[i][j][k] = n;
					continue;
				}
				to[i][j][k] = to[i][j - 1][to[i][j - 1][k]];
				add[i][j][k] = add[i][j - 1][k] + add[i][j - 1][to[i][j - 1][k]];
				if (lim[i][j - 1][to[i][j - 1][k]] == inf) lim[i][j][k] = lim[i][j - 1][k];
				else lim[i][j][k] = min(1LL * lim[i][j - 1][k], max(0LL, 1LL * lim[i][j - 1][to[i][j - 1][k]] - add[i][j - 1][k]));	
			}
		}
	}
	return;
}

long long simulate(int x, int _z) {
	long long z = _z;
	while (x != n) {
		int c = 0;
		while (c + 1 < lg10 && pw[c + 1] <= z) c++;
		for (int j = lg2 - 1; j >= 0; j--) {
			if (lim[c][j][x] != inf && z >= lim[c][j][x]) continue;
			if (to[c][j][x] == n) continue;
			z += add[c][j][x];
			x = to[c][j][x];
		}
		if (x == n) break;
		if (z >= s[x]) {
			z += s[x];
			x = w[x];
		} else {
			z += p[x];
			x = l[x];
		}
	}
	return z;
}

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