Submission #1196372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196372		belgianbot	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	996 ms	2162688 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 50001;
const int LOG = 26;
vector<long long> win(MAX_N);
vector<vector<vector<long long>>> dist, nxt, mini;
set<long long> temp;
vector<int> s,p,w,l;
int n;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	s = ss; p = pp; w = ww; l = ll; n = nn;
	l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n);
	
	for (int i = 0; i < n; i++) temp.insert((long long)(s[i]));

	dist.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size())));
	nxt.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size())));
	mini.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size())));

	auto it = temp.begin();
	for (int i = 0; i < (int)(temp.size()); i++, it++){
		for (int j = 0; j <= n; j++) {
			if ((long long)(s[j]) >= *it) {
				dist[j][0][i] = p[j];
				nxt[j][0][i] = l[j];
				mini[j][0][i] = s[l[j]];
			}else {
				dist[j][0][i] = s[j];
				nxt[j][0][i] = w[j];
				mini[j][0][i] = *it;
			}
		}
	}
	
	for (int i = 0; i < (int)(temp.size()); i++){
		for (int j = 0; j <= n; j++) {
			for (int k = 1; k < LOG; k++) {
				dist[j][k][i] = dist[j][k-1][i] + dist[nxt[j][k-1][i]][k-1][i];
				nxt[j][k][i] = nxt[nxt[j][k-1][i]][k-1][i];
				mini[j][k][i] = min(mini[j][k-1][i], mini[nxt[j][k-1][i]][k-1][i]);
			}
		}
	}
	win[n] = 0;
	for (int i = n-1; i >= 0; i--) {
		win[i] = win[w[i]] + s[i];
	}
	return;
}

long long simulate(int x, int z) {
	long long st = z, pos = x;
	
	auto it = temp.begin();
	for (int i = 0; i < (int)(temp.size()); i++, it++) {
		if (st >= *it) continue;
		for (int j = LOG-1; j >= 0; j--) {
			if (st + dist[pos][j][i] >= *it) continue;
			st += dist[pos][j][i];
			pos = nxt[pos][j][i];
		}
		st += dist[pos][0][i];
		pos = nxt[pos][0][i];
		//cerr << *it << ' ' << pos << ' ' << st << '\n';
	}
	return st + win[pos];
}

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