Submission #1232847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232847		The_Samurai	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	2485 ms	1529360 KiB

dungeons

#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;

struct node {
	int tar, need;
	ll sum;

	node() {
		tar = -1;
	}

	node(int _tar, int _need, ll _sum) {
		tar = _tar; need = _need; sum = _sum;
	}
};

int n;
const int lg = 24;
vector<vector<node>> jump1, jump2;
vector<vector<vector<node>>> jump;
vector<int> s, p, w, l;
vector<int> pw;

void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
	pw = {1};
	for (int i = 1; i < 8; i++) pw.emplace_back(pw.back() * 8);
	s = _s; p = _p; w =_w; l = _l;
	n = _n;
	jump1 = vector(lg, vector(n, node()));
	jump = vector(lg / 3, vector(lg, vector(n, node())));
	for (int i = 0; i < n; i++) {
		jump1[0][i] = node(w[i], s[i], s[i]);
	}
	for (int j = 1; j < lg; j++) {
		for (int i = 0; i < n; i++) {
			if (jump1[j - 1][i].tar == n) jump1[j][i] = jump1[j - 1][i];
			else {
				auto &par = jump1[j - 1][jump1[j - 1][i].tar];
				jump1[j][i].tar = par.tar;
				jump1[j][i].sum = jump1[j - 1][i].sum + par.sum;
				jump1[j][i].need = max(jump1[j - 1][i].need, par.need - (int) min(jump1[j - 1][i].sum, (ll) 1e9));
			}
		}
	}
	for (int x = 0; x < jump.size(); x++) {
		for (int i = 0; i < n; i++) {
			if (s[i] <= pw[x]) jump[x][0][i] = node(w[i], 1e9, s[i]);
			else jump[x][0][i] = node(l[i], s[i], p[i]);
		}
		for (int j = 1; j < lg; j++) {
			for (int i = 0; i < n; i++) {
				if (jump[x][j - 1][i].tar == n) {
					jump[x][j][i] = jump[x][j - 1][i];
					continue;
				}
				auto &par = jump[x][j - 1][jump[x][j - 1][i].tar];
				jump[x][j][i] = node(par.tar, 0, par.sum + jump[x][j - 1][i].sum);
				jump[x][j][i].need = min(jump[x][j - 1][i].need, par.need - (int) min(jump[x][j - 1][i].sum, ll(1e9)));
			}
		}
	}
}

long long simulate(int x, int z) {
	ll now = z;
	while (x != n) {
		for (int i = lg - 1; i >= 0 and x < n; i--) {
			if (jump1[i][x].need <= now) {
				now += jump1[i][x].sum;
				x = jump1[i][x].tar;
			}
		}
		if (x == n) break;
		assert(jump1[0][x].need > now);
		int wh = (31 - __builtin_clz(now)) / 3;
		if (wh >= lg) return 0;
		for (int i = lg - 1; i >= 0 and x < n; i--) {
			if (now >= jump[wh][i][x].need) continue;
			now += jump[wh][i][x].sum;
			x = jump[wh][i][x].tar;
		}
		if (x == n) break;
		if (now >= s[x]) now += s[x], x = w[x];
		else now += p[x], x = l[x];
	}
	return now;
}

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