Submission #536462

#	Time	Username	Problem	Language	Result	Execution time	Memory
536462		grt	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	2015 ms	957644 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 = 1e18 + 10;
int n;
ll sum[nax][18][26];
int jp[nax][18][26];
ll lim[nax][18][26];
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; bit < 25; ++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] = 2LL * INF;
				lim[i][0][bit] = 2LL * INF;
			}
		}
		jp[n][0][bit] = n;
		lim[n][0][bit] = 2LL * 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];
				sum[i][j][bit] = min(sum[i][j][bit], INF);
				lim[i][j][bit] = min(lim[i][j - 1][bit], (lim[jp[i][j - 1][bit]][j - 1][bit] - sum[i][j - 1][bit]));
				if(lim[i][j][bit] >= 10'000'000) lim[i][j][bit] = 2LL * INF;
				lim[i][j][bit] = max(-1LL, lim[i][j][bit]);
			}
		}
	}
}

ll simulate(int x, int zp) {
	ll z = zp;
	for(int bit = 0; bit < 25; ++bit) {
		if((1 << (bit + 1)) > z || bit == 24) {
			for(int i = 17; 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];
			}
		}
	}
	assert(x == n);
	return z;
}




//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int N, Q;
	//cin >> N >> Q;
	//vi _s(N), _p(N), _w(N), _l(N);
	//for(int i = 0; i < N; ++i) cin >> _s[i];
	//for(int i = 0; i < N; ++i) cin >> _p[i];
	//for(int i = 0; i < N; ++i) cin >> _w[i];
	//for(int i = 0; i < N; ++i) cin >> _l[i];
	//init(N, _s, _p, _w, _l);
	//while(Q--) {
		//int x, z;
		//cin >> x >> z;
		//cout << simulate(x, z) << "\n";
	//}
//}

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