Submission #1026025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026025		MinaRagy06	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3960 ms	1825632 KiB

dungeons

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("Ofast")

int n;
const int N = 400'005;
const int LOG = 25, L = 3, B = 1 << L, LIFTS = 7; //LIFTS = log_B(1e7 + N)
const ll inf = 1e18;
struct node {
	int anc;
	ll strength, bound;
	node() {}
	node(int _anc, ll _strength, ll _bound) {
		anc = _anc;
		strength = _strength;
		bound = _bound;
	}
	void operator+=(const node &r) {
		//i -> l -> r
		anc = r.anc;
		bound = min(bound, r.bound - strength);
		strength += r.strength;
	}
};
vector<int> s, p, w, l;
node lift[LOG][N][LIFTS];
const int M = 1 << LOG;
int logs[M];
node cur[N][L - 1];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	logs[1] = 0;
	for (int i = 2; i < M; i++) {
		logs[i] = logs[i >> 1] + 1;
	}
	n = _n, s = _s, p = _p, w = _w, l = _l;
	s.push_back(0), p.push_back(0), w.push_back(n), l.push_back(n);
	for (int j = 0; j < LOG; j++) {
		for (int i = 0; i <= n; i++) {
			if (s[i] < (1 << j)) {
				lift[j][i][0] = node(w[i], s[i], inf);
			} else if (s[i] >= (1 << (j + 1))) {
				lift[j][i][0] = node(l[i], p[i], inf);
			} else { //log(s[i]) == log(z)
				lift[j][i][0] = node(l[i], p[i], s[i] - 1);
			}
		}
	}
	for (int j = 0; j < LOG; j++) {
		for (int k = 1; k < LIFTS; k++) {
			for (int i = 0; i <= n; i++) {
				cur[i][0] = lift[j][i][k - 1];
				cur[i][0] += lift[j][cur[i][0].anc][k - 1];
			}
			for (int o = 1; o < L - 1; o++) {
				for (int i = 0; i <= n; i++) {
					cur[i][o] = cur[i][o - 1];
					cur[i][o] += cur[cur[i][o].anc][o - 1];
				}
			}
			for (int i = 0; i <= n; i++) {
				lift[j][i][k] = cur[i][L - 2];
				lift[j][i][k] += cur[lift[j][i][k].anc][L - 2];
			}
		}
	}
}
ll simulate(int x, int _z) {
	ll z = _z;
	while (x != n) {
		if (z >= s[x]) {
			z += s[x];
			x = w[x];
		} else{
			z += p[x];
			x = l[x];
		}
		int lg = (z < M? logs[z] : LOG - 1);
		for (int k = LIFTS - 1; k >= 0; k--) {
			for (int o = 1; o < B; o++) {
				ll newz = z + lift[lg][x][k].strength;
				if (z <= lift[lg][x][k].bound && (z >= (1 << (LOG - 1)) || (newz < M && logs[newz] == lg))) {
					z += lift[lg][x][k].strength;
					x = lift[lg][x][k].anc;
				}
			}
		}
	}
	return z;
}
#ifdef MINA
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	ll st = chrono::steady_clock::now().time_since_epoch().count();
	int _n;
	cin >> _n;
	vector<int> _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);
	int q;
	cin >> q;
	while (q--) {
		int x, z;
		cin >> x >> z;
		cout << simulate(x, z) << '\n';
	}
	ll en = chrono::steady_clock::now().time_since_epoch().count();
//	cout << (en - st) / 1e9 << "s\n";
	return 0;
}
#endif

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