Submission #1242937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242937		trimkus	Dungeons Game (IOI21_dungeons)	C++20	25 / 100	337 ms	78468 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> S, P, W, L;
int N;
const int MAXN = 5e4 + 1;
vector<int> adj[MAXN + 1];
int lift[6][MAXN + 1][20];
ll to_root[MAXN + 1];
ll cost[6][MAXN + 1][20];
vector<int> vals;
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;
	S.push_back(0);
	for (int i = 0; i <= n; ++i) {
		vals.push_back(S[i]);
	}
	sort(begin(vals), end(vals));
	vals.erase(unique(begin(vals), end(vals)), end(vals));
	// cout << vals.size() << endl;
	for (int i = 0; i < n; ++i) {
		adj[w[i]].push_back(i);
	}
	auto dfs = [&](auto& dfs, int i, ll now) -> void {
		now += S[i];
		to_root[i] = now;
		for (auto& u : adj[i]) {
			dfs(dfs, u, now);
		}
	};
	dfs(dfs, n, 0);
	// for (int i = 0; i < n; ++i) {
	// 	cerr << cost[i] << " ";
	// }
	// cerr << "\n";
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j < 20; ++j) {
			for (int k = 0; k < 6; ++k) {
				lift[k][i][j] = -1;
				cost[k][i][j] = 1e18;
			}
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	if (cycle[i]) {
	// 		cerr << i << " ";
	// 	}
	// }
	// cerr << "\n";
	for (int i = 0; i < n; ++i) {
		for (int k = 0; k < vals.size(); ++k) {
			if (vals[k] < S[i]) {
				lift[k][i][0] = L[i];
				cost[k][i][0] = P[i];
			} else {
				lift[k][i][0] = W[i];
				cost[k][i][0] = S[i];
			}
		}
	}
	for (int j = 1; j < 20; ++j) {
		for (int i = 0; i < n; ++i) {
			for (int k = 0; k < 6; ++k) {
				if (lift[k][i][j - 1] == -1) continue;
				// cerr << i << "!\n";
				lift[k][i][j] = lift[k][lift[k][i][j - 1]][j - 1];
				cost[k][i][j] = cost[k][i][j - 1] + cost[k][lift[k][i][j - 1]][j - 1]; 
			}
		}
	}
	// for (int k = 0; k < (int)vals.size(); ++k) {
	// 	cout << k << ":\n";
	// 	for (int j = 0; j < 5; ++j) {
	// 		for (int i = 0; i <= n; ++i) {
	// 			cout << lift[k][i][j] << " ";
	// 		}
	// 		cout << "\n";
	// 	}
	// }
	// for (int k = 0; k < (int)vals.size(); ++k) {
	// 	cout << k << ":\n";
	// 	for (int j = 0; j < 5; ++j) {
	// 		for (int i = 0; i <= n; ++i) {
	// 			cout << cost[k][i][j] << " ";
	// 		}
	// 		cout << "\n";
	// 	}
	// }
	// for (int j = 0; j < 5; ++j) {
	// 	for (int i = 0; i <= n; ++i) {
	// 		cout << cost1[i][j] << " ";
	// 	}
	// 	cout << "\n";
	// }
	// for (int i = 0; i <= n; ++i) {
	// 	cout << cycle[i] << " ";
	// }
	// cout << "\n";
	return;
}

long long simulate(int x, int z) {
	ll res = z;
	ll tot = 0;
	// cout << x << " -> ";
	int k = 0;
	while (k < vals.size() && res >= vals[k]) k += 1;
	// cout << k << " " << res << " " << vals[k] << "\n";
	while (k < vals.size() && res < vals[k] && x != N) {
		int nk = k - 1;
		for (int i = 19; i >= 0; --i) {
			if (lift[nk][x][i] == -1) continue;
			if (cost[nk][x][i] + res >= vals[k]) continue;
			res += cost[nk][x][i];
			x = lift[nk][x][i];
		}
		if (x == N) break;
		res += cost[nk][x][0];
		x = lift[nk][x][0];
		while (k < vals.size() && res >= vals[k]) k += 1;
	}
	res += to_root[x];
	return res;
}

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