Submission #536449

#	Time	Username	Problem	Language	Result	Execution time	Memory
536449		grt	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	1683 ms	419376 KiB

dungeons

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 50 * 1000 + 10;
const ll INF = 1e9 + 10;
int n;
ll sum[nax][17][25];
int jp[nax][17][25];
ll lim[nax][17][25];
int s[nax], w[nax], l[nax], p[nax];

void init(int _n, vi _s, vi _p, vi _w, vi _l) {
	n = _n;
	for(int i = 0; i < n; ++i) {
		s[i] = _s[i];
		p[i] = _p[i];
		w[i] = _w[i];
		l[i] = _l[i];
	}
	w[n] = n; l[n] = n;
	for(int bit = 0; (1 << bit) < 10'000'000; ++bit) {
		for(int i = 0; i < n; ++i) {
			if(_s[i] > (1 << bit)) {
				jp[i][0][bit] = _l[i];
				sum[i][0][bit] = _p[i];
				lim[i][0][bit] = _s[i];
			} else {
				jp[i][0][bit] = _w[i];
				sum[i][0][bit] = _s[i];
				lim[i][0][bit] = INF;
			}
		}
		jp[n][0][bit] = n;
		lim[n][0][bit] = INF;
		for(int j = 1; j < 17; ++j) {
			for(int i = 0; i <= n; ++i) {
				jp[i][j][bit] = jp[jp[i][j - 1][bit]][j - 1][bit];
				sum[i][j][bit] = sum[jp[i][j - 1][bit]][j - 1][bit] + sum[i][j - 1][bit];
				lim[i][j][bit] = min(lim[i][j - 1][bit], (lim[jp[i][j - 1][bit]][j - 1][bit] - sum[i][j - 1][bit]));
			}
		}
	}
}

ll simulate(int x, int zp) {
	ll z = zp;
	for(int bit = 0; bit < 25; ++bit) {
		if((1 << (bit + 1)) > z) {
			for(int i = 16; i >= 0; --i) {
				if(lim[x][i][bit] >= z) {
					z += sum[x][i][bit];
					x = jp[x][i][bit];
				}
			}
			if(z >= s[x]) {
				z += s[x];
				x = w[x];
			} else {
				z += p[x];
				x = l[x];
			}
		}
	}
	return z;
}


//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
	//cerr << simulate(0, 1) << "\n";
	//cerr << simulate(2, 3) << "\n";
//}

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