Submission #1064632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064632		fv3	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	78 ms	25796 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N;
vector<int> S, P, W, L;
vector<int> win_dist;

vector<int> visited;
vector<int> cycle;

vector<vector<int>> inc;
vector<vector<int>> bl_node;
vector<vector<ll>> bl_dist;
vector<ll> cycle_length;

void binary_lifting(int index, ll total_dist, vector<int>& nodes, vector<ll>& dist)
{
	int nt = 1;
	const int sz = nodes.size();
	while (nt <= sz)
	{
		bl_node[index].push_back(nodes[sz - nt]);
		bl_dist[index].push_back(total_dist - dist[sz - nt]);
		nt <<= 1;
	}

	nodes.push_back(index);
	dist.push_back(total_dist);

	for (auto node : inc[index])
	{
		binary_lifting(node, total_dist + P[node], nodes, dist);
	}

	nodes.pop_back();
	dist.pop_back();
}

ll target;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	N = n;
	S = s; P = p; W = w; L = l;
	L.push_back(N);
	P.push_back(0);
	target = s[0];

	// Find winning distance
	win_dist = vector<int>(N+1);
	for (int i = N - 1; i >= 0; i--)
		win_dist[i] = win_dist[W[i]] + 1;

	vector<int> inc_cnt(N+1);
	for (int i = 0; i < N + 1; i++)
	{
		inc_cnt[L[i]]++;
	}

	queue<int> path_nodes;
	for (int i = 0; i < N + 1; i++)
	{
		if (!inc_cnt[i])
			path_nodes.push(i);
	}

	inc = vector<vector<int>>(N+1);
	while (!path_nodes.empty())
	{
		int s = path_nodes.front();
		path_nodes.pop();

		inc[L[s]].push_back(s);

		if (--inc_cnt[L[s]] == 0)
			path_nodes.push(L[s]);
	}

	bl_node = vector<vector<int>>(N+1);
	bl_dist = vector<vector<ll>>(N+1);
	for (int i = 0; i < N + 1; i++)
	{
		if (!inc_cnt[i] || !inc[i].size()) continue;
		vector<int> nodes;
		vector<ll> dist;
		binary_lifting(i, 0, nodes, dist);
	}

	cycle = vector<int>(N+1);
	cycle_length = vector<ll>(N+1);
	for (int i = 0; i < N+1; i++)
	{
		if (!inc_cnt[i] || cycle[i]) continue;
		vector<int> nodes;
		vector<ll> dist;

		int current_node = L[i];
		ll current_dist = P[i];
		while (current_node != i)
		{
			nodes.push_back(current_node);
			dist.push_back(current_dist);

			current_dist += p[current_node];
			current_node = L[current_node];
		}
		nodes.push_back(current_node);
		dist.push_back(current_dist);

		ll sub = 0; int cnt = 0;
		const int sz = nodes.size();
		while (!cycle[current_node])
		{
			cycle[current_node] = 1;
			cycle_length[current_node] = current_dist;
			int nt = 1;
			while (nt <= sz)
			{
				bl_node[current_node].push_back(nodes[cnt + nt-1]);
				bl_dist[current_node].push_back(dist[cnt + nt-1] - sub);
				nt <<= 1;
			}
			if (dist.size())
			{
				dist.push_back(dist.back() + p[nodes.back()]);
				nodes.push_back(L[nodes.back()]);
			}
			sub += P[current_node];
			cnt++;
			current_node = L[current_node];
		}
	}
}

ll strength;
ll simulate(int x, int z) 
{
	strength = z;
	if (x == N)
		return strength;

	while (!cycle[x] && strength < target)
	{
		const int sz = bl_node[x].size();
		for (int i = sz - 1; i >= 0; i--)
		{
			if (strength + bl_dist[x][i] >= target)
				continue;
			strength += bl_dist[x][i];
			x = bl_node[x][i];
			break;
		}

		if (strength + P[x] >= target)
		{
			strength += P[x];
			x = L[x];
		}
	}

	if (strength >= target || x == N)
		return strength + win_dist[x] * target;

	strength += cycle_length[x] * ((target - strength) / cycle_length[x]);
	while (strength < target)
	{
		const int sz = bl_node[x].size();
		for (int i = sz - 1; i >= 0; i--)
		{
			if (strength + bl_dist[x][i] >= target)
				continue;
			strength += bl_dist[x][i];
			x = bl_node[x][i];
			break;
		}

		if (strength + P[x] >= target)
		{
			strength += P[x];
			x = L[x];
		}
	}

	return strength + win_dist[x] * target;
}

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