oj.uz

Submission #437057

# Submission time Handle Problem Language Result Execution time Memory
437057 2021-06-25T17:24:33 Z schse Dungeons Game (IOI21_dungeons) C++17
13 / 100
 223 ms 43460 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 121 ms 43332 KB Output is correct
3 Correct 132 ms 43232 KB Output is correct
4 Correct 114 ms 43340 KB Output is correct
5 Correct 118 ms 43300 KB Output is correct
6 Correct 132 ms 43340 KB Output is correct
7 Correct 137 ms 43328 KB Output is correct
8 Correct 109 ms 43324 KB Output is correct
9 Correct 119 ms 43320 KB Output is correct
10 Correct 109 ms 43332 KB Output is correct
11 Correct 139 ms 43240 KB Output is correct
12 Correct 223 ms 43460 KB Output is correct
13 Correct 191 ms 43336 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 121 ms 43332 KB Output is correct
3 Correct 132 ms 43232 KB Output is correct
4 Correct 114 ms 43340 KB Output is correct
5 Correct 118 ms 43300 KB Output is correct
6 Correct 132 ms 43340 KB Output is correct
7 Correct 137 ms 43328 KB Output is correct
8 Correct 109 ms 43324 KB Output is correct
9 Correct 119 ms 43320 KB Output is correct
10 Correct 109 ms 43332 KB Output is correct
11 Correct 139 ms 43240 KB Output is correct
12 Correct 223 ms 43460 KB Output is correct
13 Correct 191 ms 43336 KB Output is correct
14 Incorrect 2 ms 1100 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 121 ms 43332 KB Output is correct
3 Correct 132 ms 43232 KB Output is correct
4 Correct 114 ms 43340 KB Output is correct
5 Correct 118 ms 43300 KB Output is correct
6 Correct 132 ms 43340 KB Output is correct
7 Correct 137 ms 43328 KB Output is correct
8 Correct 109 ms 43324 KB Output is correct
9 Correct 119 ms 43320 KB Output is correct
10 Correct 109 ms 43332 KB Output is correct
11 Correct 139 ms 43240 KB Output is correct
12 Correct 223 ms 43460 KB Output is correct
13 Correct 191 ms 43336 KB Output is correct
14 Incorrect 2 ms 1100 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -