Submission #1066261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066261		pedroslrey	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7064 ms	330180 KiB

dungeons

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;
using lli = long long;

const int MAXN = 4e5 + 10;
const int MAXK = 20;

int pjump[MAXN][MAXK];
lli psum[MAXN][MAXK];
lli pdp[MAXN][MAXK];

int sjump[MAXN][MAXK];
lli ssum[MAXN][MAXK];
lli sdp[MAXN][MAXK];

int N;

void init(int n, vector<int> ss, vector<int> ps, vector<int> ws, vector<int> ls) {
	N = n;
	ss.push_back(0);
	ps.push_back(0);
	ws.push_back(n);
	ls.push_back(n);
	++n;

	for (int i = 0; i < n; ++i) {
		pjump[i][0] = ls[i];
		psum[i][0] = ps[i];
		pdp[i][0] = min(ss[i], ss[ls[i]] - ps[i]);
	}

	for (int k = 1; k < MAXK; ++k) 
		for (int u = 0; u < n; ++u) {
			pjump[u][k] = pjump[pjump[u][k-1]][k-1];
			psum[u][k] = psum[u][k-1] + psum[pjump[u][k-1]][k-1];
			pdp[u][k] = min(pdp[u][k-1], pdp[pjump[u][k-1]][k-1] - psum[u][k-1]);
		}

	for (int i = 0; i < n; ++i) {
		sjump[i][0] = ws[i];
		ssum[i][0] = ss[i];
		sdp[i][0] = max(ss[i], ss[ws[i]] - ss[i]);
	}

	for (int k = 1; k < MAXK; ++k) 
		for (int u = 0; u < n; ++u) {
			sjump[u][k] = sjump[sjump[u][k-1]][k-1];
			ssum[u][k] = ssum[u][k-1] + ssum[sjump[u][k-1]][k-1];
			sdp[u][k] = max(sdp[u][k-1], sdp[sjump[u][k-1]][k-1] - ssum[u][k-1]);
		}
}

lli simulate(int u, int _z) {
	// cerr << "start\n";
	lli z = _z;
	bool win = false;
	while (u != N) {
		// cerr << u << " win = " << win << "\n";
		// cerr << "z = " << z << "\n";
		if (!win) {
			if (ssum[u][0] <= z) {
				win = true;
				continue;
			}
			for (int k = MAXK - 1; k >= 0; --k)
				if (pdp[u][k] > z) {
					z += psum[u][k];
					u = pjump[u][k];
				}
			z += psum[u][0];
			u = pjump[u][0];

			win = true;
		}
		else {
			if (ssum[u][0] > z) {
				win = false;
				continue;
			}
			for (int k = MAXK - 1; k >= 0; --k)
				if (sdp[u][k] <= z) {
					z += ssum[u][k];
					u = sjump[u][k];
				}
			z += ssum[u][0];
			u = sjump[u][0];

			win = false;
		}
	}

	return z;
}

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