Submission #437057

#	Time	Username	Problem	Language	Result	Execution time	Memory
437057		schse	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	223 ms	43460 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ll long long

struct node
{
	ll strength;
	ll defeat;
	ll wrom;
	ll lrom;
	pair<int, ll> above[25];
	pair<int, ll> below[25];
};
vector<node> g;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
	g.resize(n + 1);
	for (int i = 0; i < n; i++)
	{
		g[i].strength = s[i];
		g[i].defeat = p[i];
		g[i].lrom = l[i];
		g[i].wrom = w[i];
		g[i].above[0] = {w[i], s[i]};
		g[i].below[0] = {l[i], p[i]};
	}

	fill(g[n].above, g[n].above + 25, make_pair(n, 0LL));
	fill(g[n].below, g[n].below + 25, make_pair(n, 0LL));

	for (int e = 1; e < 25; e++)
	{
		for (int i = 0; i < n; i++)
		{
			auto t = g[i].above[e - 1];
			auto p = g[t.first].above[e - 1];
			g[i].above[e] = {p.first, p.second + t.second};

			t = g[i].below[e - 1];
			p = g[t.first].below[e - 1];
			g[i].below[e] = {p.first, p.second + t.second};
		}
	}
	return;
}

long long simulate(int x, int z)
{
	ll wstrength = g[0].strength;
	ll str = z;
	if (str < wstrength)
	{
		for (int i = 25 - 1; i >= 0; i--)
		{
			if (g[x].below[i].second + str < wstrength)
			{
				str += g[x].below[i].second;
				x = g[x].below[i].first;
			}
		}
		if (x == g.size() - 1)
			return str;
		str += g[x].defeat;
		x = g[x].lrom;
		if (x == g.size() - 1)
			return str;
	}

	str += g[x].above[24].second;
	return str;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:66:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if (x == g.size() - 1)
      |       ~~^~~~~~~~~~~~~~~
dungeons.cpp:70:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   if (x == g.size() - 1)
      |       ~~^~~~~~~~~~~~~~~

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