Submission #1197794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197794		belgianbot	Dungeons Game (IOI21_dungeons)	C++20	24 / 100	7113 ms	2162688 KiB

dungeons

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

const int LOG = 25;
int divi;
vector<vector<vector<long long>>> distW, nxtW, miniW, distL, nxtL, miniL;
vector<long long> win, lim;
vector<int> sorted;
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;
	divi = min(7, n+1);

	distW.resize(n+1, vector<vector<long long>>(LOG,vector<long long>(divi)));
	nxtW.resize(n+1, vector<vector<long long>>(LOG,vector<long long>(divi)));
	miniW.resize(n+1, vector<vector<long long>>(LOG,vector<long long>(divi)));
	distL.resize(n+1, vector<vector<long long>>(LOG,vector<long long>(divi)));
	nxtL.resize(n+1, vector<vector<long long>>(LOG,vector<long long>(divi)));
	miniL.resize(n+1, vector<vector<long long>>(LOG,vector<long long>(divi)));
	sorted.resize(n);
	win.resize(n+1);

	sorted = s;
	sort(sorted.begin(), sorted.end());
	lim.resize(divi);
	lim[0] = 0;
	for (int i = 1; i < divi; i++) {
		lim[i] = (long long)(sorted[(n/(divi-1)) * i]);
	}
	lim[divi-1] = (long long)(sorted[n-1]);
	l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n);
	for (int i = 0; i < divi; i++) {
		for (int j = 0; j <= n; j++) {
			distW[j][0][i] = s[j];
			nxtW[j][0][i] = w[j];
			miniW[j][0][i] = s[w[j]] - s[j];
			if ((long long)(s[j]) < lim[i]) {
				distL[j][0][i] = s[j];
				nxtL[j][0][i] = w[j];
				if ((long long) (s[w[j]]) < lim[i]) miniL[j][0][i] = LLONG_MAX;
				else miniL[j][0][i] = s[w[j]] - s[j];
			}
			else {
				distL[j][0][i] = p[j];
				nxtL[j][0][i] = l[j];
				if ((long long) (s[l[j]]) < lim[i]) miniL[j][0][i] = LLONG_MAX;
				else miniL[j][0][i] = s[l[j]] - p[j];
			}
			
		}
	}
	for (int l = 0; l < divi; l++) {
		for (int k = 1; k < LOG; k++){
			for (int j = 0; j <= n; j++) {
				distW[j][k][l] = distW[j][k-1][l] + distW[nxtW[j][k-1][l]][k-1][l];
				nxtW[j][k][l] = nxtW[nxtW[j][k-1][l]][k-1][l];
				miniW[j][k][l] = max(miniW[j][k-1][l], miniW[nxtW[j][k-1][l]][k-1][l] - distW[j][k-1][l]);
				distL[j][k][l] = distL[j][k-1][l] + distL[nxtL[j][k-1][l]][k-1][l];
				nxtL[j][k][l] = nxtL[nxtL[j][k-1][l]][k-1][l];
				miniL[j][k][l] = min(miniL[j][k-1][l], miniL[nxtL[j][k-1][l]][k-1][l] - distL[j][k-1][l]);
			}
		}
	}

	//for (int x : lim) cerr << x << ' ';
	//cerr << '\n';
	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;
	int pos = x;
	
	while (pos != n) {
		//cerr << pos << ' ' << st << '\n';
		int curr = upper_bound(lim.begin(), lim.end(), st) - lim.begin() - 1;
		//cerr << curr << '\n';
		if (st >= lim.back()) break;
		if (st < s[pos]) {
			for (int i = LOG-1; i >= 0; i--) {
				if (st >= miniL[pos][i][curr]) continue;
				st += distL[pos][i][curr];
				pos = nxtL[pos][i][curr];
			}
			st += distL[pos][0][curr];
			pos = nxtL[pos][0][curr];
		}
		else {
			for (int i = LOG-1; i >= 0; i--) {
				if (st < miniW[pos][i][0]) continue;
				st += distW[pos][i][0];
				pos = nxtW[pos][i][0];
			}
			st += distW[pos][0][0];
			pos = nxtW[pos][0][0];
		}
	}
	//cerr << pos << ' ' << st << '\n';
	return st + win[pos];
}

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