oj.uz

Submission #794652

# Submission time Handle Problem Language Result Execution time Memory
794652 2023-07-26T18:26:28 Z Johann Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2971 ms 1014660 KB 
#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;
};
typedef vector<info> vinf;
typedef vector<vinf> vvinf;
typedef vector<vvinf> vvvinf;
vvvinf lifts;

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));
	Svalues.push_back(1);
	while (Svalues.back() <= maxi)
		Svalues.push_back(Svalues.back() * 8);

	dpWin.assign(N + 1, INF);
	dpWin[N] = 0;
	for (int i = N - 1; i >= 0; --i)
		dpWin[i] = S[i] + dpWin[W[i]];

	lifts.resize(sz(Svalues) - 1); // assuming  having reached Svalues[i] but not Svalues[i + 1]

	for (int ii = 0; ii < sz(lifts); ++ii)
	{
		// potentially to small for a good lift
		lifts[ii] = vvinf(N, vinf(ceil(log2(Svalues[ii]) + 1)));
		for (int i = 0; i < N; ++i)
			if (S[i] >= Svalues[ii])
				lifts[ii][i][0] = {L[i], P[i], min(Svalues[ii + 1], S[i])};
			else
				lifts[ii][i][0] = {W[i], S[i], Svalues[ii + 1]};

		for (int j = 1; j < sz(lifts[ii].back()); ++j)
			for (int i = 0; i < N; ++i)
			{
				int mid = lifts[ii][i][j - 1].node;
				if (mid == N)
					lifts[ii][i][j] = lifts[ii][i][j - 1];
				else
					lifts[ii][i][j] = {lifts[ii][mid][j - 1].node,
									   lifts[ii][mid][j - 1].gain + lifts[ii][i][j - 1].gain,
									   min(lifts[ii][i][j - 1].needed, lifts[ii][mid][j - 1].needed - lifts[ii][i][j - 1].gain)};
			}
	}

	return;
}

void step(int &node, ll &z)
{
	if (S[node] > z)
	{
		z += P[node];
		node = L[node];
	}
	else
	{
		z += S[node];
		node = W[node];
	}
}
long long simulate(int x, int z)
{
	ll ans = z;
	int ii = 0;
	while (ii < sz(lifts) && x != N)
	{
		if (ans >= Svalues[ii + 1])
			++ii;
		else
		{
			assert(ans >= Svalues[ii]);

			for (int j = sz(lifts[ii][x]) - 1; j >= 0 && x != N; --j)
			{
				if (lifts[ii][x][j].needed > ans)
				{
					ans += lifts[ii][x][j].gain;
					x = lifts[ii][x][j].node;
				}
			}
			if (x != N)
				step(x, ans);
		}
	}

	return ans + dpWin[x];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 62 ms 54120 KB Output is correct
5 Correct 3 ms 2412 KB Output is correct
6 Correct 62 ms 53936 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 1425 ms 1009964 KB Output is correct
3 Correct 1233 ms 1009924 KB Output is correct
4 Correct 1004 ms 789192 KB Output is correct
5 Correct 1095 ms 788004 KB Output is correct
6 Correct 1769 ms 1007460 KB Output is correct
7 Correct 2075 ms 1005952 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2788 KB Output is correct
2 Correct 156 ms 127108 KB Output is correct
3 Correct 150 ms 127236 KB Output is correct
4 Correct 30 ms 6864 KB Output is correct
5 Correct 34 ms 13548 KB Output is correct
6 Correct 225 ms 126328 KB Output is correct
7 Correct 266 ms 126304 KB Output is correct
8 Correct 34 ms 13568 KB Output is correct
9 Correct 30 ms 6868 KB Output is correct
10 Correct 31 ms 6864 KB Output is correct
11 Correct 636 ms 126284 KB Output is correct
12 Correct 2762 ms 126220 KB Output is correct
13 Correct 2661 ms 126332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2788 KB Output is correct
2 Correct 156 ms 127108 KB Output is correct
3 Correct 150 ms 127236 KB Output is correct
4 Correct 30 ms 6864 KB Output is correct
5 Correct 34 ms 13548 KB Output is correct
6 Correct 225 ms 126328 KB Output is correct
7 Correct 266 ms 126304 KB Output is correct
8 Correct 34 ms 13568 KB Output is correct
9 Correct 30 ms 6868 KB Output is correct
10 Correct 31 ms 6864 KB Output is correct
11 Correct 636 ms 126284 KB Output is correct
12 Correct 2762 ms 126220 KB Output is correct
13 Correct 2661 ms 126332 KB Output is correct
14 Correct 4 ms 2772 KB Output is correct
15 Correct 138 ms 126304 KB Output is correct
16 Correct 149 ms 126332 KB Output is correct
17 Correct 112 ms 98540 KB Output is correct
18 Correct 158 ms 126332 KB Output is correct
19 Correct 185 ms 126284 KB Output is correct
20 Correct 182 ms 98488 KB Output is correct
21 Correct 258 ms 126232 KB Output is correct
22 Correct 479 ms 126284 KB Output is correct
23 Correct 1182 ms 98432 KB Output is correct
24 Correct 1480 ms 126260 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2788 KB Output is correct
2 Correct 156 ms 127108 KB Output is correct
3 Correct 150 ms 127236 KB Output is correct
4 Correct 30 ms 6864 KB Output is correct
5 Correct 34 ms 13548 KB Output is correct
6 Correct 225 ms 126328 KB Output is correct
7 Correct 266 ms 126304 KB Output is correct
8 Correct 34 ms 13568 KB Output is correct
9 Correct 30 ms 6868 KB Output is correct
10 Correct 31 ms 6864 KB Output is correct
11 Correct 636 ms 126284 KB Output is correct
12 Correct 2762 ms 126220 KB Output is correct
13 Correct 2661 ms 126332 KB Output is correct
14 Correct 4 ms 2772 KB Output is correct
15 Correct 138 ms 126304 KB Output is correct
16 Correct 149 ms 126332 KB Output is correct
17 Correct 112 ms 98540 KB Output is correct
18 Correct 158 ms 126332 KB Output is correct
19 Correct 185 ms 126284 KB Output is correct
20 Correct 182 ms 98488 KB Output is correct
21 Correct 258 ms 126232 KB Output is correct
22 Correct 479 ms 126284 KB Output is correct
23 Correct 1182 ms 98432 KB Output is correct
24 Correct 1480 ms 126260 KB Output is correct
25 Correct 114 ms 125520 KB Output is correct
26 Correct 146 ms 126284 KB Output is correct
27 Correct 136 ms 126260 KB Output is correct
28 Correct 131 ms 126284 KB Output is correct
29 Correct 157 ms 126332 KB Output is correct
30 Correct 257 ms 126284 KB Output is correct
31 Correct 311 ms 126328 KB Output is correct
32 Correct 346 ms 98544 KB Output is correct
33 Correct 292 ms 126160 KB Output is correct
34 Correct 704 ms 126168 KB Output is correct
35 Correct 303 ms 126216 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 1425 ms 1009964 KB Output is correct
3 Correct 1233 ms 1009924 KB Output is correct
4 Correct 1004 ms 789192 KB Output is correct
5 Correct 1095 ms 788004 KB Output is correct
6 Correct 1769 ms 1007460 KB Output is correct
7 Correct 2075 ms 1005952 KB Output is correct
8 Correct 2 ms 2788 KB Output is correct
9 Correct 156 ms 127108 KB Output is correct
10 Correct 150 ms 127236 KB Output is correct
11 Correct 30 ms 6864 KB Output is correct
12 Correct 34 ms 13548 KB Output is correct
13 Correct 225 ms 126328 KB Output is correct
14 Correct 266 ms 126304 KB Output is correct
15 Correct 34 ms 13568 KB Output is correct
16 Correct 30 ms 6868 KB Output is correct
17 Correct 31 ms 6864 KB Output is correct
18 Correct 636 ms 126284 KB Output is correct
19 Correct 2762 ms 126220 KB Output is correct
20 Correct 2661 ms 126332 KB Output is correct
21 Correct 4 ms 2772 KB Output is correct
22 Correct 138 ms 126304 KB Output is correct
23 Correct 149 ms 126332 KB Output is correct
24 Correct 112 ms 98540 KB Output is correct
25 Correct 158 ms 126332 KB Output is correct
26 Correct 185 ms 126284 KB Output is correct
27 Correct 182 ms 98488 KB Output is correct
28 Correct 258 ms 126232 KB Output is correct
29 Correct 479 ms 126284 KB Output is correct
30 Correct 1182 ms 98432 KB Output is correct
31 Correct 1480 ms 126260 KB Output is correct
32 Correct 114 ms 125520 KB Output is correct
33 Correct 146 ms 126284 KB Output is correct
34 Correct 136 ms 126260 KB Output is correct
35 Correct 131 ms 126284 KB Output is correct
36 Correct 157 ms 126332 KB Output is correct
37 Correct 257 ms 126284 KB Output is correct
38 Correct 311 ms 126328 KB Output is correct
39 Correct 346 ms 98544 KB Output is correct
40 Correct 292 ms 126160 KB Output is correct
41 Correct 704 ms 126168 KB Output is correct
42 Correct 303 ms 126216 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 3 ms 2772 KB Output is correct
45 Correct 1510 ms 1014660 KB Output is correct
46 Correct 1717 ms 1010024 KB Output is correct
47 Correct 1303 ms 1010500 KB Output is correct
48 Correct 1280 ms 1012636 KB Output is correct
49 Correct 1532 ms 1014648 KB Output is correct
50 Correct 1556 ms 1012264 KB Output is correct
51 Correct 1299 ms 1012608 KB Output is correct
52 Correct 1592 ms 1010340 KB Output is correct
53 Correct 2399 ms 788800 KB Output is correct
54 Correct 1986 ms 1012124 KB Output is correct
55 Correct 2971 ms 1010940 KB Output is correct
56 Correct 2208 ms 1009404 KB Output is correct
57 Correct 2538 ms 1008300 KB Output is correct
58 Correct 2220 ms 1007028 KB Output is correct
59 Correct 2242 ms 1005620 KB Output is correct
60 Correct 2500 ms 1004076 KB Output is correct
61 Correct 2357 ms 1003012 KB Output is correct