Submission #1064383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064383		fv3	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	385 ms	4444 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> dist;

void find_dist(int index)
{
	if (dist[index]) return;
	if (W[index] == N)
	{
		dist[index] = 1;
		return;
	}
	find_dist(W[index]);
	dist[index] = dist[W[index]] + 1;
}

ll target;
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;
	target = s[0];

	dist = vector<int>(N);
	for (int i = 0; i < N; i++)
		find_dist(i);
}

ll strength;
vector<int> visited;
queue<int> order;
int cur;

void sim()
{
	if (visited[cur] || cur == N || strength >= target) return;
	visited[cur] = 1;

	order.push(cur);
	strength += P[cur];
	cur = L[cur];

	sim();
}

void final(int index)
{
	if (index == N) return;
	if (strength >= S[index])
	{
		strength += target * dist[cur];
	}
	else
	{
		strength += P[index];
		final(L[index]);
	}
}
ll simulate(int x, int z) 
{
	strength = z;
	cur = x;
	visited = vector<int>(N);
	order = {};

	sim();

	if (cur == N)
		return strength;

	if (strength >= target)
	{
		final(cur);
		return strength;
	}


	while (order.front() != cur)
		order.pop();

	ll cycle_length = 0;
	while (!order.empty())
	{
		cycle_length += P[order.front()];
		order.pop();
	}

	strength += ((target - strength) / cycle_length) * cycle_length;
	final(cur);
	return strength;
}

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