Submission #775297

#	Time	Username	Problem	Language	Result	Execution time	Memory
775297		SanguineChameleon	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3355 ms	1091372 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 4e5 + 20;
const int maxT = 9;
const int maxK = 25;
const int inf = 1e9 + 20;
pair<int, pair<int, int>> jump[maxT][maxN][maxK];
long long rem[maxN];
int S[maxN];
int P[maxN];
int W[maxN];
int L[maxN];
vector<int> times;
int N, T;

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L) {
	N = _N;
	for (int i = 0; i < N; i++) {
		S[i] = _S[i];
		P[i] = _P[i];
		W[i] = _W[i];
		L[i] = _L[i];
	}
	W[N] = N;
	for (int i = 0; i < maxT; i++) {
		times.push_back(1 << (i * 3));
	}
	sort(times.begin(), times.end());
	T = times.size();
	for (int t = 0; t < T; t++) {
		for (int i = 0; i < N; i++) {
			if (t > 0 && S[i] <= times[t - 1]) {
				jump[t][i][0].first = W[i];
				jump[t][i][0].second.first = S[i];
				jump[t][i][0].second.second = -inf;
			}
			else {
				jump[t][i][0].first = L[i];
				jump[t][i][0].second.first = P[i];
				jump[t][i][0].second.second = -S[i];
			}
		}
		jump[t][N][0].first = N;
		jump[t][N][0].second.first = 0;
		jump[t][N][0].second.second = -inf;
		for (int k = 1; k < maxK; k++) {
			jump[t][N][k].first = N;
			jump[t][N][k].second.first = 0;
			jump[t][N][k].second.second = -inf;
			for (int i = 0; i < N; i++) {
				int nxt = jump[t][i][k - 1].first;
				jump[t][i][k].first = jump[t][nxt][k - 1].first;
				jump[t][i][k].second.first = min(inf, jump[t][i][k - 1].second.first + jump[t][nxt][k - 1].second.first);
				jump[t][i][k].second.second = max(jump[t][i][k - 1].second.second, jump[t][i][k - 1].second.first + jump[t][nxt][k - 1].second.second);
			}
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		rem[i] = rem[W[i]] + S[i];
	}
	return;
}

long long simulate(int X, int _Z) {
	long long Z = _Z;
	int t = 0;
	while (X != N) {
		while (t < T && times[t] <= Z) {
			t++;
		}
		if (t == T) {
			break;
		}
		int sum = 0;
		for (int k = maxK - 1; k >= 0; k--) {
			if (sum + jump[t][X][k].second.first < inf && Z + jump[t][X][k].second.second < 0) {
				Z += jump[t][X][k].second.first;
				sum += jump[t][X][k].second.first;
				X = jump[t][X][k].first;
			}
		}
		if (Z >= S[X]) {
			Z += S[X];
			X = W[X];
		}
		else {
			Z += P[X];
			X = L[X];
		}
	}
	return Z + rem[X];
}

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