Submission #818550

#	Time	Username	Problem	Language	Result	Execution time	Memory
818550		LittleCube	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7044 ms	215580 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

namespace
{

	struct node
	{
		// value, min required initial value
		ll v, m;
	};

	node merge(node l, node r)
	{
		auto [lv, lm] = l;
		auto [rv, rm] = r;
		return node{lv + rv, max(lm, rm - lv)};
	}

	const int P = 25;
	int n, m;
	int id[400001][P];
	node go[400001][P];
	vector<int> s, p, w, l;
}

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;

	for (int i = 0; i < n; i++)
		go[i][0] = node{s[i], s[i]}, id[i][0] = w[i];

	go[n][0] = node{0, 0}, id[n][0] = n;
	for (int k = 0; k + 1 < P; k++)
		for (int i = 0; i <= n; i++)
			go[i][k + 1] = merge(go[i][k], go[id[i][k]][k]), id[i][k + 1] = id[id[i][k]][k];

	return;
}

ll simulate(int x, int _z)
{
	ll z = _z;
	while (x != n)
	{
		for (int k = P - 1; k >= 0; k--)
			if (go[x][k].m <= z)
				z += go[x][k].v, x = id[x][k];
		if (x != n)
		{
			z += p[x];
			x = l[x];
		}
	}
	return z;
}

Compilation message (stderr)

dungeons.cpp:26:9: warning: '{anonymous}::m' defined but not used [-Wunused-variable]
   26 |  int n, m;
      |         ^

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