oj.uz

Submission #1048739

# Submission time Handle Problem Language Result Execution time Memory
1048739 2024-08-08T09:19:10 Z DorostWef Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 2064992 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define F first
#define S second
#define mk make_pair
typedef pair <ll, ll> pii;
const int N = 400023, LG = 24, L2 = 9, K = 5;
int s[N], p[N], o[N], l[N], n;
long long m[N], a[N];
pair <int, pii> nx[LG][N][L2];
const ll INF = 1e18;

void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
	n = nn;
	for (int i = 0; i < n; i++) {
		s[i] = ss[i];
		p[i] = pp[i];
		o[i] = ww[i];
		l[i] = ll[i];
	}
	m[n] = 0;
	a[n] = 0;
	l[n] = n;
	o[n] = n;
	s[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		a[i] = a[o[i]] + s[i];
		m[i] = max((long long)s[i], m[o[i]] - s[i]);
	}
	for (int w = 0; w < LG; w++) {
		for (int i = 0; i <= n; i++) {
			if (i < n && s[i] <= (1 << w)) {
				nx[w][i][0].F = o[i];
				nx[w][i][0].S.F = INF;
				nx[w][i][0].S.S = s[i];
			} else {
				nx[w][i][0].F = l[i];
				nx[w][i][0].S.F = s[i] - 1;
				nx[w][i][0].S.S = p[i];
			}
		}
		for (int j = 1; j < L2; j++) {
			for (int i = 0; i <= n; i++) {
				nx[w][i][j].S.S = nx[w][i][j - 1].S.S;
				nx[w][i][j].S.F = nx[w][i][j - 1].S.F;
				nx[w][i][j].F = nx[w][i][j - 1].F;
				for (int k = 0; k < K; k++) {
					int y = nx[w][i][j].F;
					nx[w][i][j].F = nx[w][y][j - 1].F;
					nx[w][i][j].S.F = min (nx[w][i][j].S.F, nx[w][y][j - 1].S.F - nx[w][i][j].S.S);
					nx[w][i][j].S.S = nx[w][i][j].S.S + nx[w][y][j - 1].S.S;
				}
			}
		}
	}
	return;
}

pair <int, long long> findd (int w, int x, ll z) {
	for (int i = L2 - 1; i >= 0; i--) {
		for (int k = 0; k < K; k++) {
			if (z <= nx[w][x][i].S.F) {
				z += nx[w][x][i].S.S;
				x = nx[w][x][i].F;
			}
		}
	}
	return {x, z};
}

ll ans (int x, ll z) {
	if (z >= m[x])
		return z + a[x];
	int l = 0;
	while ((1 << l) < s[x])
		l++;
	pair <int, ll> pp = findd (l, x, z);
	x = pp.F;
	z = pp.S;
	return ans (x, z);
}

long long simulate(int x, int z) {
	pair <int, ll> pp = findd (0, x, z);
	x = pp.F;
	z = pp.S;
	ll w = ans (x, z);
	return w;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 57692 KB Output is correct
2 Correct 4 ms 57692 KB Output is correct
3 Correct 9 ms 68360 KB Output is correct
4 Correct 199 ms 288692 KB Output is correct
5 Correct 10 ms 68444 KB Output is correct
6 Correct 197 ms 288808 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 68188 KB Output is correct
2 Correct 3458 ms 2059992 KB Output is correct
3 Correct 3124 ms 2061900 KB Output is correct
4 Correct 2943 ms 2063004 KB Output is correct
5 Correct 2429 ms 2063120 KB Output is correct
6 Correct 3631 ms 2061740 KB Output is correct
7 Correct 3231 ms 2060368 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 68188 KB Output is correct
2 Correct 245 ms 290008 KB Output is correct
3 Correct 202 ms 290232 KB Output is correct
4 Correct 201 ms 289620 KB Output is correct
5 Correct 193 ms 289600 KB Output is correct
6 Correct 240 ms 289856 KB Output is correct
7 Correct 242 ms 289676 KB Output is correct
8 Correct 192 ms 289360 KB Output is correct
9 Correct 198 ms 289392 KB Output is correct
10 Correct 201 ms 289240 KB Output is correct
11 Correct 372 ms 289692 KB Output is correct
12 Correct 469 ms 289856 KB Output is correct
13 Correct 249 ms 289620 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 68188 KB Output is correct
2 Correct 245 ms 290008 KB Output is correct
3 Correct 202 ms 290232 KB Output is correct
4 Correct 201 ms 289620 KB Output is correct
5 Correct 193 ms 289600 KB Output is correct
6 Correct 240 ms 289856 KB Output is correct
7 Correct 242 ms 289676 KB Output is correct
8 Correct 192 ms 289360 KB Output is correct
9 Correct 198 ms 289392 KB Output is correct
10 Correct 201 ms 289240 KB Output is correct
11 Correct 372 ms 289692 KB Output is correct
12 Correct 469 ms 289856 KB Output is correct
13 Correct 249 ms 289620 KB Output is correct
14 Correct 7 ms 68184 KB Output is correct
15 Correct 220 ms 288576 KB Output is correct
16 Correct 262 ms 289872 KB Output is correct
17 Correct 210 ms 289604 KB Output is correct
18 Correct 229 ms 289616 KB Output is correct
19 Correct 241 ms 289616 KB Output is correct
20 Correct 235 ms 289616 KB Output is correct
21 Correct 211 ms 289620 KB Output is correct
22 Correct 219 ms 289620 KB Output is correct
23 Correct 349 ms 289620 KB Output is correct
24 Correct 422 ms 289680 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 68188 KB Output is correct
2 Correct 245 ms 290008 KB Output is correct
3 Correct 202 ms 290232 KB Output is correct
4 Correct 201 ms 289620 KB Output is correct
5 Correct 193 ms 289600 KB Output is correct
6 Correct 240 ms 289856 KB Output is correct
7 Correct 242 ms 289676 KB Output is correct
8 Correct 192 ms 289360 KB Output is correct
9 Correct 198 ms 289392 KB Output is correct
10 Correct 201 ms 289240 KB Output is correct
11 Correct 372 ms 289692 KB Output is correct
12 Correct 469 ms 289856 KB Output is correct
13 Correct 249 ms 289620 KB Output is correct
14 Correct 7 ms 68184 KB Output is correct
15 Correct 220 ms 288576 KB Output is correct
16 Correct 262 ms 289872 KB Output is correct
17 Correct 210 ms 289604 KB Output is correct
18 Correct 229 ms 289616 KB Output is correct
19 Correct 241 ms 289616 KB Output is correct
20 Correct 235 ms 289616 KB Output is correct
21 Correct 211 ms 289620 KB Output is correct
22 Correct 219 ms 289620 KB Output is correct
23 Correct 349 ms 289620 KB Output is correct
24 Correct 422 ms 289680 KB Output is correct
25 Correct 231 ms 289104 KB Output is correct
26 Correct 240 ms 289960 KB Output is correct
27 Correct 220 ms 289664 KB Output is correct
28 Correct 222 ms 289600 KB Output is correct
29 Correct 250 ms 287824 KB Output is correct
30 Correct 270 ms 289752 KB Output is correct
31 Correct 287 ms 289360 KB Output is correct
32 Correct 433 ms 289620 KB Output is correct
33 Correct 281 ms 289616 KB Output is correct
34 Correct 551 ms 289616 KB Output is correct
35 Correct 319 ms 287572 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 68188 KB Output is correct
2 Correct 3458 ms 2059992 KB Output is correct
3 Correct 3124 ms 2061900 KB Output is correct
4 Correct 2943 ms 2063004 KB Output is correct
5 Correct 2429 ms 2063120 KB Output is correct
6 Correct 3631 ms 2061740 KB Output is correct
7 Correct 3231 ms 2060368 KB Output is correct
8 Correct 8 ms 68188 KB Output is correct
9 Correct 245 ms 290008 KB Output is correct
10 Correct 202 ms 290232 KB Output is correct
11 Correct 201 ms 289620 KB Output is correct
12 Correct 193 ms 289600 KB Output is correct
13 Correct 240 ms 289856 KB Output is correct
14 Correct 242 ms 289676 KB Output is correct
15 Correct 192 ms 289360 KB Output is correct
16 Correct 198 ms 289392 KB Output is correct
17 Correct 201 ms 289240 KB Output is correct
18 Correct 372 ms 289692 KB Output is correct
19 Correct 469 ms 289856 KB Output is correct
20 Correct 249 ms 289620 KB Output is correct
21 Correct 7 ms 68184 KB Output is correct
22 Correct 220 ms 288576 KB Output is correct
23 Correct 262 ms 289872 KB Output is correct
24 Correct 210 ms 289604 KB Output is correct
25 Correct 229 ms 289616 KB Output is correct
26 Correct 241 ms 289616 KB Output is correct
27 Correct 235 ms 289616 KB Output is correct
28 Correct 211 ms 289620 KB Output is correct
29 Correct 219 ms 289620 KB Output is correct
30 Correct 349 ms 289620 KB Output is correct
31 Correct 422 ms 289680 KB Output is correct
32 Correct 231 ms 289104 KB Output is correct
33 Correct 240 ms 289960 KB Output is correct
34 Correct 220 ms 289664 KB Output is correct
35 Correct 222 ms 289600 KB Output is correct
36 Correct 250 ms 287824 KB Output is correct
37 Correct 270 ms 289752 KB Output is correct
38 Correct 287 ms 289360 KB Output is correct
39 Correct 433 ms 289620 KB Output is correct
40 Correct 281 ms 289616 KB Output is correct
41 Correct 551 ms 289616 KB Output is correct
42 Correct 319 ms 287572 KB Output is correct
43 Correct 4 ms 57692 KB Output is correct
44 Correct 7 ms 68188 KB Output is correct
45 Correct 3608 ms 2064992 KB Output is correct
46 Correct 2650 ms 2061344 KB Output is correct
47 Correct 2814 ms 2061704 KB Output is correct
48 Correct 2392 ms 2063160 KB Output is correct
49 Correct 3842 ms 2064972 KB Output is correct
50 Correct 3396 ms 2061564 KB Output is correct
51 Correct 2269 ms 2059680 KB Output is correct
52 Correct 3520 ms 2055248 KB Output is correct
53 Execution timed out 7119 ms 1211204 KB Time limit exceeded
54 Halted 0 ms 0 KB -