Submission #1243066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243066		trimkus	Dungeons Game (IOI21_dungeons)	C++20	26 / 100	420 ms	212044 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 = 4e5 + 1;
vector<int> adj[MAXN + 1];
int lift[MAXN + 1][20];
ll to_root[MAXN + 1];
ll cost[MAXN + 1][20];
ll str[MAXN + 1][20];
ll MAXS;



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);
	// cout << vals.size() << endl;
	for (int i = 0; i < n; ++i) {
		adj[w[i]].push_back(i);
		MAXS = max(MAXS, 1LL * S[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) {
			lift[i][j] = -1;
			cost[i][j] = 1e18;
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	if (cycle[i]) {
	// 		cerr << i << " ";
	// 	}
	// }
	// cerr << "\n";
	for (int i = 0; i < n; ++i) {
		lift[i][0] = W[i];
		cost[i][0] = S[i];
		str[i][0] = S[i];
	}
	for (int j = 1; j < 20; ++j) {
		for (int i = 0; i < n; ++i) {
			if (lift[i][j - 1] == -1) continue;
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
			cost[i][j] = cost[i][j - 1] + cost[lift[i][j - 1]][j - 1];
			str[i][j] = max(str[i][j - 1], str[lift[i][j - 1]][j - 1]);
		}
	}
	// for (int j = 0; j < 5; ++j) {
	// 	for (int i = 0; i < n; ++i) {
	// 		cerr << lift[i][j] << " ";
	// 	}
	// 	cerr << "\n";
	// }
	// for (int j = 0; j < 5; ++j) {
	// 	for (int i = 0; i < n; ++i) {
	// 		cerr << cost[i][j] << " ";
	// 	}
	// 	cerr << "\n";
	// }
	return;
}


long long simulate(int x, int z) {
	ll res = z;
	ll tot = 0;
	// cout << x << " -> ";
	while (res < MAXS && x != N) {
		for (int i = 19; i >= 0 && x != N; --i) {
			if (lift[x][i] == -1) continue;
			if (str[x][i] < res) {
				res += cost[x][i];
				x = lift[x][i];
			}
		}
		if (x == N) break;
		if (S[x] > res) {
			res += S[x];
			x = L[x];
		} else {
			res += S[x];
			x = W[x];
		}
	}
	res += to_root[x];
	// cout << res << " -> ";
	// cout << to_root[x] << "\n";
	// res += to_root[x];
	return res;
}

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