Submission #466883

#	Time	Username	Problem	Language	Result	Execution time	Memory
466883		alexxela12345	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6344 ms	1515596 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <cassert>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

const int B = 8;
const int LG = 30;

struct mdata {
	int v;
	ll  mxdelta, gained;
};

mdata merge(const mdata &a, const mdata &b) {
	return {b.v, max(a.mxdelta, b.mxdelta + a.gained), a.gained + b.gained};
}

int n;
vector<int> s, p, w, l;
vector<vector<vector<mdata>>> up;

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
	n = n_ + 1;
	s = s_;
	s.push_back(0);
	p = p_;
	p.push_back(0);
	w = w_;
	w.push_back(n - 1);
	l = l_;
	l.push_back(n - 1);
	up.resize(LG / B + 1, vector<vector<mdata>> (n, vector<mdata> (LG)));
	for (int i = 0; i * B < LG; i++) {
		int k = 1 << (i * B);
		for (int v = 0; v < n; v++) {
			if (s[v] < k) {
				up[i][v][0] = {w[v], -INF, s[v]};
			} else {
				up[i][v][0] = {l[v], -s[v], p[v]};
			}
		}
		for (int j = 1; j < LG; j++) {
			for (int v = 0; v < n; v++) {
				up[i][v][j] = merge(up[i][v][j - 1], up[i][up[i][v][j - 1].v][j - 1]);
			}
		}
	}
}

ll simulate(int v, int z_) {
	ll z = z_;
	int k = 0;
	while (v != n - 1) {
		while (k < LG / B && (1 << ((k + 1) * B)) <= z) {
			k++;
		}
		for (int i = LG - 1; i >= 0; i--) {
			if (z + up[k][v][i].mxdelta < 0) {
				z += up[k][v][i].gained;
				v = up[k][v][i].v;
			}
		}
		assert(z >= s[v]);
		z += s[v];
		v = w[v];
	}
	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