Submission #453071

#	Time	Username	Problem	Language	Result	Execution time	Memory
453071		ComPhyPark	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7204 ms	1432264 KiB

dungeons

#include"dungeons.h"
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef struct st {
	int x, z, t;
	st() { x = 0; z = t = 0; }
	st(int X, int Z, int T) { x = X; z = Z; t = T; }
}st;
int n;
st l[400001][300];
int sv[400001], pv[400001], wv[400001], lv[400001];
ll w[400001];
int p2[26] = { 1 };
const int BIG = 33554432;
int min(int a, int b) {
	return a < b ? a : b;
}
int max(int a, int b) {
	return a > b ? a : b;
}
int f(int a, int b, int c) {
	if (b < c)return 0;
	return a < (b - c) ? a : (b - c);
}
void init(int N, vector<int>S, vector<int>P, vector<int>W, vector<int>L) {
	int i, j, k = 0, k2;
	n = N;
	w[n] = 0;
	L.push_back(n);
	W.push_back(n);
	P.push_back(0);
	S.push_back(0);
	for (i = 0; i <= n; i++) {
		lv[i] = L[i];
		wv[i] = W[i];
		pv[i] = P[i];
		sv[i] = S[i];
	}
	st p, q;
	for (i = n - 1; i >= 0; i--) {
		w[i] = w[W[i]] + S[i];
	}
	for (k = 0; k < 24; k++) {
		p2[k + 1] = p2[k] << 1;
		k2 = k * (k + 1) / 2;
		for (i = 0; i <= n; i++) {
			if (sv[i] <= p2[k]) {
				l[i][k2] = st(wv[i], sv[i], BIG);
			}
			else {
				l[i][k2] = st(lv[i], pv[i], sv[i]);
			}
		}
		for (j = 0; j < k; j++) {
			for (i = 0; i <= n; i++) {
				p = l[i][j + k2];
				q = l[p.x][j + k2];
				l[i][j + 1 + k2] = st(q.x, min(BIG, p.z + q.z), max(0, min(p.t, q.t - p.z)));
			}
		}
	}
}
ll simulate(int x, int z) {
	int i, j, k;
	ll r = z;
	st p;
	for (i = 0; i < 24; i++) {
		if (x == n)break;
		if (r >= p2[i + 1])continue;
		k = i * (i + 1) / 2;
		for (j = i; j >= 0; j--) {
			if (x == n)break;
			p = l[x][k + j];
			if (r < p.t && r + p.z < p2[i + 1]) {
				r += p.z;
				x = p.x;
			}
		}
		if (x == n)break;
		if (r < sv[x]) {
			r += pv[x];
			x = lv[x];
		}
		else {
			r += sv[x];
			x = wv[x];
		}
	}
	return r + w[x];
}

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