Submission #1205912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205912		mickey080929	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	3162 ms	921728 KiB

dungeons

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

using namespace std;
typedef long long ll;

const int lg2 = 8;
const int lg = 24;
const int inf = 1e9;
const int MAXN = 400010;

int N;
int sum[lg2][MAXN][lg];
int mn[lg2][MAXN][lg];
int pos[lg2][MAXN][lg];
ll dist[MAXN];
int S[MAXN], W[MAXN];

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];
		W[i] = w[i];
	}
	for (int i=0; i<lg2; i++) {
		for (int j=0; j<N; j++) {
			if (s[j] < (1<<(3*i))) {
				mn[i][j][0] = inf;
				sum[i][j][0] = s[j];
				pos[i][j][0] = w[j];
			}
			else {
				mn[i][j][0] = s[j];
				sum[i][j][0] = p[j];
				pos[i][j][0] = l[j];
			}
		}
		mn[i][N][0] = inf;
		sum[i][N][0] = 0;
		pos[i][N][0] = N;
		for (int lv=1; lv<lg; lv++) {
			for (int j=0; j<=N; j++) {
				int nxt = pos[i][j][lv-1];
				mn[i][j][lv] = mn[i][j][lv-1];
				if (mn[i][nxt][lv-1] != inf) {
					if (mn[i][nxt][lv-1] <= sum[i][j][lv-1])
						mn[i][j][lv] = 0;
					else mn[i][j][lv] = min(mn[i][j][lv], mn[i][nxt][lv-1] - (int)sum[i][j][lv-1]);
				}
				sum[i][j][lv] = min(inf, sum[i][j][lv-1] + sum[i][nxt][lv-1]);
				pos[i][j][lv] = pos[i][nxt][lv-1];
			}
		}
	}
	dist[N] = 0;
	for (int i=N-1; i>=0; i--) {
		dist[i] = dist[w[i]] + (ll)s[i];
	}
	return;
}

ll simulate(int x, int z) {
	ll Z = z;
	for (int i=0; i<lg2; i++) {
		for (int rep=0; rep<7; rep++) {
			if (Z >= (1<<(3*i+3))) break;
			for (int lv=lg-1; lv>=0; lv--) {
				if (mn[i][x][lv] > Z && sum[i][x][lv] < inf) {
					Z += (ll)sum[i][x][lv];
					x = pos[i][x][lv];
				}
			}
			if (x == N) return Z;
			Z += (ll)S[x];
			x = W[x];
			if (x == N) return Z;
		}
	}
	return Z + dist[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