Submission #615210

#	Time	Username	Problem	Language	Result	Execution time	Memory
615210		SeDunion	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3411 ms	1597032 KiB

dungeons

#include "dungeons.h"
#include <assert.h>
#include <vector>
 
using namespace std;
using ll = long long;
 
const ll inf = 1e18;
 
const int N = 400'005;
const int LOGN = 25;
const int LOGK = 9;
 
int wh[LOGK][LOGN][N];
ll sf[LOGK][LOGN][N];
ll nd[LOGK][LOGN][N];
 
int s[N];
int p[N];
int w[N];
int l[N];
 
int n;
 
void init(int n_, vector<int>s_, vector<int>p_, vector<int>w_, vector<int>l_) {
	n = n_;
	s_.emplace_back(0), p_.emplace_back(0), w_.emplace_back(n), l_.emplace_back(n);
	for (int i = 0 ; i <= n ; ++ i) {
		s[i] = s_[i], p[i] = p_[i], w[i] = w_[i], l[i] = l_[i];
	}
	for (int k = 1 ; k < LOGK ; ++ k) {
		for (int v = 0 ; v <= n ; ++ v) {
			int i = 0;
			if (s[v] < (1ll << (ll)(k*3))) {
				wh[k][i][v] = w[v];
				sf[k][i][v] = s[v];
				nd[k][i][v] = inf;
			} else {
				wh[k][i][v] = l[v];
				sf[k][i][v] = p[v];
				nd[k][i][v] = s[v];
			}
		}
		for (int i = 0 ; i+1 < LOGN ; ++ i) {
			for (int v = 0 ; v <= n ; ++ v) {
				int t = wh[k][i][v];
				wh[k][i+1][v] = wh[k][i][t];
				sf[k][i+1][v] = sf[k][i][v] + sf[k][i][t];
				nd[k][i+1][v] = min(nd[k][i][v], nd[k][i][t]-sf[k][i][v]);
			}
		}
	}
}
 
ll simulate(int x, int z_) {
	ll z = z_;
	int cnt = 0;
	ll k = 0;
	while (x < n) {
		cnt++;
		while (k < LOGK - 1 && (1ll << (((ll)k + 1ll)*3)) <= z) ++k;
		for (int i = LOGN - 1 ; i >= 0 ; -- i) {
			if (nd[k][i][x] > z) {
				z += sf[k][i][x];
				x = wh[k][i][x];
			}
		}
		if (s[x] <= z) {
			z += s[x];
			x = w[x];
		} else {
			z += p[x];
			x = l[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