Submission #794196

#	Time	Username	Problem	Language	Result	Execution time	Memory
794196		Johann	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7038 ms	270372 KiB

dungeons

#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<vvpii> vvvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;
const ll INF = 1LL << 60;
vi S, P;
vi Svalues;
vector<int> W, L;
vi dpWin;
struct info
{
	int node;
	ll gain;
	ll needed;
};
vector<vector<info>> lift;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
	N = n;
	S.resize(N), P.resize(N);
	W = w, L = l;
	for (int i = 0; i < N; ++i)
		S[i] = s[i], P[i] = p[i];

	int maxi = *max_element(all(S));

	lift.assign(N, vector<info>(ceil(log2(maxi) + 1)));

	for (int i = 0; i < N; ++i)
	{
		lift[i][0].node = W[i];
		lift[i][0].gain = S[i];
		lift[i][0].needed = S[i];
	}
	for (int j = 1; j < sz(lift[0]); ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			int mid = lift[i][j - 1].node;
			if (mid == N)
				lift[i][j] = lift[i][j - 1];
			else
			{
				lift[i][j].node = lift[mid][j - 1].node;
				lift[i][j].gain = lift[i][j - 1].gain + lift[mid][j - 1].gain;
				lift[i][j].needed = max(lift[i][j - 1].needed, lift[mid][j - 1].needed - lift[i][j - 1].gain);
			}
		}
	}

	return;
}

long long simulate(int x, int z)
{
	ll ans = z;
	while (x != N)
	{
		if (ans < lift[x][0].needed)
		{
			ans += P[x];
			x = L[x];
		}
		else
		{
			for (int j = sz(lift[x]) - 1; j >= 0; --j)
			{
				if (lift[x][j].needed <= ans)
				{
					ans += lift[x][j].gain;
					x = lift[x][j].node;
					break;
				}
			}
		}
	}

	return ans;
}

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