Submission #565173

#	Time	Username	Problem	Language	Result	Execution time	Memory
565173		teraqqq	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2838 ms	823692 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using ll = long long;

const int INF = 1e9;

const int N = 4e5+7;
const int B = 16;
const int W = 7; // exp = B^0, B^1, ..., B^{W-1}
const int L = 24; // jump 2^0, 2^1, ..., d^{L-1}

struct Jump {
	int go, max_exp, fadd;
} jmp[W][L][N];

ll cost_last[N];
int n;
vi s, p, w, l;

void unite(const Jump& a, const Jump& b, Jump& res) {
	res.fadd = a.fadd + b.fadd;
	res.go = b.go;
	res.max_exp = min(a.max_exp, b.max_exp - a.fadd);

	res.max_exp = max(res.max_exp, 0);
	res.fadd    = min(res.fadd,    INF);
}

void init(int _n, vi _s, vi _p, vi _w, vi _l) {
	n = _n;
	s = _s;
	p = _p;
	w = _w;
	l = _l;

	for (int i = n; i--; ) {
		cost_last[i] = cost_last[w[i]] + s[i];
	}

	for (int jexp = 0, exp = 1; jexp < W; ++jexp, exp *= B) {
		for (int i = 0; i < n; ++i) {
			Jump& jm = jmp[jexp][0][i];

			if (exp >= s[i]) {
				jm.go = w[i];
				jm.max_exp = INF;
				jm.fadd = s[i];
			} else {
				jm.go = l[i];
				jm.max_exp = s[i] - 1;
				jm.fadd = p[i];
			}
		}

		jmp[jexp][0][n].fadd = 0;
		jmp[jexp][0][n].go = n;
		jmp[jexp][0][n].max_exp = INF;

		for (int k = 1; k < L; ++k) {
			for (int i = 0; i < n; ++i) {
				const Jump& ja = jmp[jexp][k-1][i];
				unite(ja, jmp[jexp][k-1][ja.go], jmp[jexp][k][i]);
			}
		}
	}

	return;
}

ll simulate(int x, int _z) {
	ll z = _z;

	while (z < 1e7) {
		int jexp = 0, exp = 1;

		while ((ll)exp*B <= z) exp *= B, jexp++;

		for (int t = L; t--; ) {
			Jump& jm = jmp[jexp][t][x];

			if (z <= jm.max_exp) {
				z += jm.fadd;
				x =  jm.go;
			}
		}

		if (x == n) return z;

		if (z < s[x]) {
			z += p[x];
			x = l[x]; 
		} else {
			z += s[x];
			x = w[x];
		}
	}

	z += cost_last[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