Submission #438178

#	Time	Username	Problem	Language	Result	Execution time	Memory
438178		JustasZ	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	917 ms	1013004 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<vector<vector<ll> > >sum(400001, vector<vector<ll> >(25));
vector<vector<vector<int> > >jump(400001, vector<vector<int> >(25));
int n;
vector<int>s, p, w, l;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n = N;
	s = S, p = P, w = W, l = L;

	for (int i = 0; i <= n; i++) {
		for (int grp = 0; grp < 25; grp++) {
			sum[i][grp] = vector<ll>(grp + 1, 0);
			jump[i][grp] = vector<int>(grp + 1, -1);
		}
	}

	for (int grp = 0; grp < 25; grp++) {
		int upto = 1 << grp;
		vector<int>nodes;
		vector<int>in_grp(n + 1);
		for (int i = 0; i < n; i++) {
			if (s[i] <= upto || p[i] <= upto) {
				nodes.pb(i);
				in_grp[i] = 1;
			}
		}
		for (int jmp = 0; jmp < grp; jmp++) {
			for (int i : nodes) {
				if (jmp == 0) {
					int to;
					if (s[i] <= upto) {
						sum[i][grp][0] = s[i];
						to = w[i];
					} else {
						sum[i][grp][0] = p[i];
						to = l[i];
					}

					if (in_grp[to]) {
						jump[i][grp][0] = to;
					} else {
						jump[i][grp][0] = -1;
					}
				} else {
					int x = jump[i][grp][jmp - 1];
					if (x != -1) {
						sum[i][grp][jmp] = sum[i][grp][jmp - 1] + sum[x][grp][jmp - 1];
						jump[i][grp][jmp] = jump[x][grp][jmp - 1];
					} else {
						jump[i][grp][jmp] = -1;
					}
				}
			}
		}
	}
}

ll simulate(int x, int z) {
	ll cur_sum = z;
	int cur = x;
	for (int grp = 0; grp < 25; grp++) {
		ll group_lower_bound = 1 << grp;
		if (cur_sum >= group_lower_bound * 2) {
			continue;
		}
		assert(cur_sum >= group_lower_bound);
		for (int jmp = grp; jmp >= 0; jmp--) {
			if (jump[cur][grp][jmp] == -1 || (grp != 24 && cur_sum + sum[cur][grp][jmp] >= group_lower_bound * 2)) {
				continue;
			}
			cur_sum += sum[cur][grp][jmp];
			cur = jump[cur][grp][jmp];
		}

		if (cur_sum >= s[cur]) {
			cur_sum += s[cur];
			cur = w[cur];
		} else {
			cur_sum += p[cur];
			cur = l[cur];
		}

		if (cur == n) {
			return cur_sum;
		}
	}
	exit(3);
	return -1;
}

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