Submission #1113098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113098		siewjh	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2328 ms	1435768 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 400005;
int nums, nxt[20][9][MAXN];
ll sa[MAXN], pa[MAXN], wa[MAXN], la[MAXN], gain[20][9][MAXN], md[20][9][MAXN];
void init(int n, vector<int> sv, vector<int> pv, vector<int> wv, vector<int> lv){
	nums = n;
	for (int i = 0; i < nums; i++){
		sa[i] = sv[i]; pa[i] = pv[i]; wa[i] = wv[i]; la[i] = lv[i];
	}
	for (int b = 0; b <= 8; b++){
		ll str = 1ll << (3 * b);
		for (int i = 0; i < nums; i++){
			if (str >= sa[i]) nxt[0][b][i] = wa[i], gain[0][b][i] = sa[i], md[0][b][i] = 1e18;
			else nxt[0][b][i] = la[i], gain[0][b][i] = pa[i], md[0][b][i] = sa[i];
		}
		for (int k = 1; k <= 19; k++)
			for (int i = 0; i < nums; i++){
				int nn = nxt[k - 1][b][i];
				if (nn == nums) nxt[k][b][i] = nums;
				else{
					md[k][b][i] = min(md[k - 1][b][i], md[k - 1][b][nn] - gain[k - 1][b][i]);
					nxt[k][b][i] = nxt[k - 1][b][nn];
					gain[k][b][i] = gain[k - 1][b][i] + gain[k - 1][b][nn];
				}
			}
	}
}
ll simulate(int x, int z) {
	ll str = z, lim = 8;
	for (int b = 0; x != nums;){
		if (b != 8 && str >= lim){
			b++; lim <<= 3; continue;
		}
		for (int k = 19; k >= 0; k--){
			if (nxt[k][b][x] == nums || str >= md[k][b][x]) continue;
			str += gain[k][b][x];
			x = nxt[k][b][x];
		}
		if (str >= sa[x]) str += sa[x], x = wa[x];
		else str += pa[x], x = la[x];
	}
	return str;
}

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