Submission #1242921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242921		trimkus	Dungeons Game (IOI21_dungeons)	C++20	13 / 100	88 ms	31364 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];
ll cost[MAXN + 1];
ll cycle_cost[MAXN + 1];
bool cycle[MAXN + 1];
int lift[MAXN + 1][20], lift1[MAXN + 1][20];
ll cost1[MAXN + 1][20];
ll cyc_cost[MAXN + 1][20];
int len[MAXN + 1];


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) {
		adj[w[i]].push_back(i);
	}
	auto dfs = [&](auto& dfs, int i, ll now) -> void {
		now += S[i];
		cost[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";
	vector<bool> vis(n);
	for (int i = 0; i < n; ++i) {
		if (vis[i]) continue;
		int j = i;
		while (!vis[j]) {
			vis[j] = true;
			j = L[j];
		}
		if (cycle[j]) continue;
		int y = j;
		ll tot = 0;
		// cerr << y << "\n";
		bool ok = true;
		int now = 0;
		do {
			if (cycle[y] || y == n) {
				ok = false;
				break;
			}
			tot += P[y];
			y = L[y];
			now += 1;
		} while (y != j);
		if (!ok) continue;
		do {
			len[y] = now;
			cycle[y] = 1;
			cycle_cost[y] = tot;
			y = L[y];
		} while (y != j);
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j < 20; ++j) {
			lift[i][j] = -1;
			cost1[i][j] = 1e18;
			cyc_cost[i][j] = 1e18;
			lift1[i][j] = -1;
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	if (cycle[i]) {
	// 		cerr << i << " ";
	// 	}
	// }
	// cerr << "\n";
	for (int i = 0; i < n; ++i) {
		if (cycle[i]) continue;
		lift[i][0] = L[i];
		cost1[i][0] = P[i];
	}
	for (int i = 0; i < n; ++i) {
		if (lift[L[i]][0] != -1) {
			// cerr << i << " !\n";
			lift[i][0] = L[i];
			cost1[i][0] = P[i];
		}
	}
	for (int j = 1; j < 20; ++j) {
		for (int i = 0; i < n; ++i) {
			if (lift[i][j - 1] == -1) continue;
			// cerr << i << "!\n";
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
			cost1[i][j] = cost1[i][j - 1] + cost1[lift[i][j - 1]][j - 1]; 
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!cycle[i]) continue;
		lift1[i][0] = L[i];
		cyc_cost[i][0] = P[i];
	}
	for (int j = 1; j < 20; ++j) {
		for (int i = 0; i < n; ++i) {
			if (lift1[i][j - 1] == -1) continue;
			if ((1LL << j) > len[i]) continue;
			// cerr << i << "!\n";
			lift1[i][j] = lift1[lift1[i][j - 1]][j - 1];
			cyc_cost[i][j] = cyc_cost[i][j - 1] + cyc_cost[lift1[i][j - 1]][j - 1]; 
		}
	}
	// for (int j = 0; j < 5; ++j) {
	// 	for (int i = 0; i <= n; ++i) {
	// 		cout << lift[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 << " -> ";
	if (!cycle[x]) {
		for (int i = 19; i >= 0; --i) {
			if (lift[x][i] == -1) continue;
			if (res + cost1[x][i] >= S[0]) continue;
			// cout << i << " = " << lift[x][i] << " " << cost1[x][i] << "\n";
			// cerr << "a\n";
			res += cost1[x][i];
			x = lift[x][i];
		}
		// if (lift[x][0] != -1) x = lift[x][0];
		// cout << x << " -> ";
		while (x != N && res < S[0] && !cycle[x]) {
			res += P[x];
			x = L[x];
		}
	}
	// cerr << x << "\n";
	if (x == N) return res;
	if (res >= S[0]) {
		return res + cost[x];
	}
	// cerr << x << " " << res << " " << tot << "\n";
	tot = cycle_cost[x];
	// cerr << x << " " << cycle_cost[x] << " " << (S[0] - res) / tot * tot << "\n";

	// cerr << tot << " ";
	res += (S[0] - res) / tot * tot;
	// cerr << res << " " << "\n";
	for (int i = 19; i >= 0; --i) {
		if (lift1[x][i] == -1) continue;
		if (res + cyc_cost[x][i] >= S[0]) continue;
		// cout << i << " = " << lift[x][i] << " " << cost1[x][i] << "\n";
		// cerr << "a\n";
		res += cyc_cost[x][i];
		x = lift1[x][i];
	}
	// if (lift[x][0] != -1) x = lift[x][0];
	// cout << x << " -> ";
	while (x != N && res < S[0]) {
		res += P[x];
		x = L[x];
	}
	// cerr << res << " " << x << "\n";
	res += cost[x];
	return res;
}

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