Submission #615153

#	Time	Username	Problem	Language	Result	Execution time	Memory
615153		SeDunion	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	1124 ms	795580 KiB

dungeons

#include "dungeons.h"
#include <assert.h>
#include <vector>
 
using namespace std;
using ll = long long;
 
const ll inf = 1e18;
 
const int N = 50123;
const int LOGN = 16;
const int LOGK = 25;
 
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] < (1 << k)) {
				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;
	while (x < n) {
		cnt++;
		if (cnt > 30) assert(0);
		int k = 0;
		while ((1ll << ((ll)k + 1ll)) <= z) ++k;
		k = min(k, LOGK - 1);
		for (int i = LOGN - 1 ; i >= 0 ; -- i) {
			if (nd[k][i][x] > z) {
				z += sf[k][i][x];
				x = wh[k][i][x];
			}
		}
		for (int rep = 0 ; rep < 10 ; ++ rep) {
			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: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11