oj.uz

Submission #1048778

# Submission time Handle Problem Language Result Execution time Memory
1048778 2024-08-08T09:31:14 Z DorostWef Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1277208 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

typedef long long ll;
#define F first
#define S second
#define mk make_pair
typedef pair <int, int> pii;
const int N = 400023, LG = 24, L2 = 11, K = 4;
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 = 1e8;
				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;
					int wef = nx[w][y][j - 1].S.F - nx[w][i][j].S.S;
					if (wef < 0)
						wef = -1;
					nx[w][i][j].S.F = min (nx[w][i][j].S.F, wef);
					nx[w][i][j].S.S = min ({(int)1e9, 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) {
	if (z <= nx[w][x][L2 - 1].S.F) {
		z += nx[w][x][L2 - 1].S.S;
		x = nx[w][x][L2 - 1].F;
	}
	for (int i = L2 - 2; 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 57832 KB Output is correct
3 Correct 8 ms 66140 KB Output is correct
4 Correct 138 ms 191316 KB Output is correct
5 Correct 8 ms 66144 KB Output is correct
6 Correct 146 ms 186136 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 62216 KB Output is correct
2 Correct 1704 ms 1266460 KB Output is correct
3 Correct 1545 ms 1266060 KB Output is correct
4 Correct 1544 ms 1266080 KB Output is correct
5 Correct 1854 ms 1266200 KB Output is correct
6 Correct 1669 ms 1266020 KB Output is correct
7 Correct 1551 ms 1266148 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 62040 KB Output is correct
2 Correct 184 ms 191208 KB Output is correct
3 Correct 207 ms 191420 KB Output is correct
4 Correct 141 ms 193248 KB Output is correct
5 Correct 156 ms 193504 KB Output is correct
6 Correct 202 ms 193528 KB Output is correct
7 Correct 224 ms 193332 KB Output is correct
8 Correct 137 ms 194384 KB Output is correct
9 Correct 158 ms 192336 KB Output is correct
10 Correct 135 ms 192052 KB Output is correct
11 Correct 239 ms 194564 KB Output is correct
12 Correct 337 ms 194256 KB Output is correct
13 Correct 190 ms 194644 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 62040 KB Output is correct
2 Correct 184 ms 191208 KB Output is correct
3 Correct 207 ms 191420 KB Output is correct
4 Correct 141 ms 193248 KB Output is correct
5 Correct 156 ms 193504 KB Output is correct
6 Correct 202 ms 193528 KB Output is correct
7 Correct 224 ms 193332 KB Output is correct
8 Correct 137 ms 194384 KB Output is correct
9 Correct 158 ms 192336 KB Output is correct
10 Correct 135 ms 192052 KB Output is correct
11 Correct 239 ms 194564 KB Output is correct
12 Correct 337 ms 194256 KB Output is correct
13 Correct 190 ms 194644 KB Output is correct
14 Correct 8 ms 62044 KB Output is correct
15 Correct 173 ms 194628 KB Output is correct
16 Correct 177 ms 194988 KB Output is correct
17 Correct 162 ms 194388 KB Output is correct
18 Correct 154 ms 192580 KB Output is correct
19 Correct 161 ms 192596 KB Output is correct
20 Correct 167 ms 192188 KB Output is correct
21 Correct 138 ms 192316 KB Output is correct
22 Correct 179 ms 192328 KB Output is correct
23 Correct 237 ms 192460 KB Output is correct
24 Correct 298 ms 192704 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 62040 KB Output is correct
2 Correct 184 ms 191208 KB Output is correct
3 Correct 207 ms 191420 KB Output is correct
4 Correct 141 ms 193248 KB Output is correct
5 Correct 156 ms 193504 KB Output is correct
6 Correct 202 ms 193528 KB Output is correct
7 Correct 224 ms 193332 KB Output is correct
8 Correct 137 ms 194384 KB Output is correct
9 Correct 158 ms 192336 KB Output is correct
10 Correct 135 ms 192052 KB Output is correct
11 Correct 239 ms 194564 KB Output is correct
12 Correct 337 ms 194256 KB Output is correct
13 Correct 190 ms 194644 KB Output is correct
14 Correct 8 ms 62044 KB Output is correct
15 Correct 173 ms 194628 KB Output is correct
16 Correct 177 ms 194988 KB Output is correct
17 Correct 162 ms 194388 KB Output is correct
18 Correct 154 ms 192580 KB Output is correct
19 Correct 161 ms 192596 KB Output is correct
20 Correct 167 ms 192188 KB Output is correct
21 Correct 138 ms 192316 KB Output is correct
22 Correct 179 ms 192328 KB Output is correct
23 Correct 237 ms 192460 KB Output is correct
24 Correct 298 ms 192704 KB Output is correct
25 Correct 158 ms 193856 KB Output is correct
26 Correct 183 ms 192944 KB Output is correct
27 Correct 144 ms 192344 KB Output is correct
28 Correct 174 ms 192428 KB Output is correct
29 Correct 202 ms 192840 KB Output is correct
30 Correct 170 ms 192592 KB Output is correct
31 Correct 196 ms 192328 KB Output is correct
32 Correct 313 ms 192320 KB Output is correct
33 Correct 228 ms 192404 KB Output is correct
34 Correct 437 ms 192372 KB Output is correct
35 Correct 210 ms 192544 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 62216 KB Output is correct
2 Correct 1704 ms 1266460 KB Output is correct
3 Correct 1545 ms 1266060 KB Output is correct
4 Correct 1544 ms 1266080 KB Output is correct
5 Correct 1854 ms 1266200 KB Output is correct
6 Correct 1669 ms 1266020 KB Output is correct
7 Correct 1551 ms 1266148 KB Output is correct
8 Correct 7 ms 62040 KB Output is correct
9 Correct 184 ms 191208 KB Output is correct
10 Correct 207 ms 191420 KB Output is correct
11 Correct 141 ms 193248 KB Output is correct
12 Correct 156 ms 193504 KB Output is correct
13 Correct 202 ms 193528 KB Output is correct
14 Correct 224 ms 193332 KB Output is correct
15 Correct 137 ms 194384 KB Output is correct
16 Correct 158 ms 192336 KB Output is correct
17 Correct 135 ms 192052 KB Output is correct
18 Correct 239 ms 194564 KB Output is correct
19 Correct 337 ms 194256 KB Output is correct
20 Correct 190 ms 194644 KB Output is correct
21 Correct 8 ms 62044 KB Output is correct
22 Correct 173 ms 194628 KB Output is correct
23 Correct 177 ms 194988 KB Output is correct
24 Correct 162 ms 194388 KB Output is correct
25 Correct 154 ms 192580 KB Output is correct
26 Correct 161 ms 192596 KB Output is correct
27 Correct 167 ms 192188 KB Output is correct
28 Correct 138 ms 192316 KB Output is correct
29 Correct 179 ms 192328 KB Output is correct
30 Correct 237 ms 192460 KB Output is correct
31 Correct 298 ms 192704 KB Output is correct
32 Correct 158 ms 193856 KB Output is correct
33 Correct 183 ms 192944 KB Output is correct
34 Correct 144 ms 192344 KB Output is correct
35 Correct 174 ms 192428 KB Output is correct
36 Correct 202 ms 192840 KB Output is correct
37 Correct 170 ms 192592 KB Output is correct
38 Correct 196 ms 192328 KB Output is correct
39 Correct 313 ms 192320 KB Output is correct
40 Correct 228 ms 192404 KB Output is correct
41 Correct 437 ms 192372 KB Output is correct
42 Correct 210 ms 192544 KB Output is correct
43 Correct 4 ms 57688 KB Output is correct
44 Correct 6 ms 62160 KB Output is correct
45 Correct 2477 ms 1277208 KB Output is correct
46 Correct 1686 ms 1272628 KB Output is correct
47 Correct 1652 ms 1273240 KB Output is correct
48 Correct 1544 ms 1275124 KB Output is correct
49 Correct 2349 ms 1275664 KB Output is correct
50 Correct 1540 ms 1270840 KB Output is correct
51 Correct 1498 ms 1267412 KB Output is correct
52 Correct 1527 ms 1267200 KB Output is correct
53 Execution timed out 7091 ms 1267716 KB Time limit exceeded
54 Halted 0 ms 0 KB -