Submission #794472

#	Time	Username	Problem	Language	Result	Execution time	Memory
794472		Johann	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7055 ms	521904 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>> liftWin;
vector<vector<info>> liftLos;

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));

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

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

	liftLos.assign(N, vector<info>(ceil(log2(maxi) + 1)));
	for (int i = 0; i < N; ++i)
	{
		liftLos[i][0].node = L[i];
		liftLos[i][0].gain = P[i];
		liftLos[i][0].needed = S[i];
	}
	for (int j = 1; j < sz(liftLos[0]); ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			int mid = liftLos[i][j - 1].node;
			if (mid == N)
				liftLos[i][j] = liftLos[i][j - 1];
			else
			{
				liftLos[i][j].node = liftLos[mid][j - 1].node;
				liftLos[i][j].gain = liftLos[i][j - 1].gain + liftLos[mid][j - 1].gain;
				liftLos[i][j].needed = min(liftLos[i][j - 1].needed, liftLos[mid][j - 1].needed - liftLos[i][j - 1].gain);
			}
		}
	}

	return;
}

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

	return ans;
}

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