oj.uz

Submission #609977

# Submission time Handle Problem Language Result Execution time Memory
609977 2022-07-28T03:52:42 Z Temmie Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4123 ms 1459276 KB 
#include <bits/stdc++.h>

int n;
std::vector <int> s, p, w, l;

struct Index {
	int dest;
	long long plus;
	long long consr;
} bin[8][19][400'005];

void init(int _n, std::vector <int> _s, std::vector <int> _p, std::vector <int> _w, std::vector <int> _l) {
	n = _n;
	s = _s;
	p = _p;
	w = _w;
	l = _l;
	for (int b = 0; b < 8; b++) {
		for (int i = 0; i < n; i++) {
			if (s[i] < (1 << (b << 3))) {
				bin[b][0][i] = w[i] == n ? (Index) { -1, 0, 0 } : (Index) { w[i], s[i], 1LL << 60 };
			} else {
				bin[b][0][i] = l[i] == n ? (Index) { -1, 0, 0 } : (Index) { l[i], p[i], s[i] };
			}
		}
	}
	for (int b1 = 0; b1 < 8; b1++) {
		for (int b2 = 1; b2 < 19; b2++) {
			for (int i = 0; i < n; i++) {
				bin[b1][b2][i] = bin[b1][b2 - 1][i].dest == -1 || bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].dest == -1 ? (Index) { -1, 0, 0 } :
				(Index) { bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].dest, bin[b1][b2 - 1][i].plus + bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].plus, std::min(bin[b1][b2 - 1][i].consr, bin[b1][b2 - 1][bin[b1][b2 - 1][i].dest].consr - bin[b1][b2 - 1][i].plus) };
			}
		}
	}
}

long long simulate(int x, int z) {
	long long ans = z;
	for (int b1 = 0; x < n; ) {
		while (b1 + 1 < 8 && ans >= (1 << ((b1 + 1) << 3))) {
			b1++;
		}
		for (int b2 = 18; ~b2; b2--) {
			if (bin[b1][b2][x].dest != -1 && ans < bin[b1][b2][x].consr) {
				ans += bin[b1][b2][x].plus;
				x = bin[b1][b2][x].dest;
			}
		}
		if (ans >= s[x]) {
			ans += s[x];
			x = w[x];
		} else {
			ans += p[x];
			x = l[x];
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 5 ms 8772 KB Output is correct
4 Correct 100 ms 182620 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 96 ms 182664 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 996 ms 1448428 KB Output is correct
3 Correct 928 ms 1450472 KB Output is correct
4 Correct 955 ms 1450564 KB Output is correct
5 Correct 1063 ms 1449932 KB Output is correct
6 Correct 1184 ms 1449864 KB Output is correct
7 Correct 1638 ms 1449660 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 189 ms 184248 KB Output is correct
3 Correct 173 ms 184300 KB Output is correct
4 Correct 132 ms 183920 KB Output is correct
5 Correct 135 ms 183900 KB Output is correct
6 Correct 197 ms 183884 KB Output is correct
7 Correct 313 ms 183868 KB Output is correct
8 Correct 199 ms 183832 KB Output is correct
9 Correct 149 ms 183984 KB Output is correct
10 Correct 234 ms 183820 KB Output is correct
11 Correct 171 ms 183848 KB Output is correct
12 Correct 2167 ms 183852 KB Output is correct
13 Correct 2091 ms 183884 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 189 ms 184248 KB Output is correct
3 Correct 173 ms 184300 KB Output is correct
4 Correct 132 ms 183920 KB Output is correct
5 Correct 135 ms 183900 KB Output is correct
6 Correct 197 ms 183884 KB Output is correct
7 Correct 313 ms 183868 KB Output is correct
8 Correct 199 ms 183832 KB Output is correct
9 Correct 149 ms 183984 KB Output is correct
10 Correct 234 ms 183820 KB Output is correct
11 Correct 171 ms 183848 KB Output is correct
12 Correct 2167 ms 183852 KB Output is correct
13 Correct 2091 ms 183884 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 142 ms 183804 KB Output is correct
16 Correct 224 ms 184168 KB Output is correct
17 Correct 147 ms 183928 KB Output is correct
18 Correct 141 ms 183860 KB Output is correct
19 Correct 192 ms 183964 KB Output is correct
20 Correct 323 ms 183840 KB Output is correct
21 Correct 360 ms 183876 KB Output is correct
22 Correct 736 ms 184040 KB Output is correct
23 Correct 163 ms 183848 KB Output is correct
24 Correct 447 ms 183864 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 189 ms 184248 KB Output is correct
3 Correct 173 ms 184300 KB Output is correct
4 Correct 132 ms 183920 KB Output is correct
5 Correct 135 ms 183900 KB Output is correct
6 Correct 197 ms 183884 KB Output is correct
7 Correct 313 ms 183868 KB Output is correct
8 Correct 199 ms 183832 KB Output is correct
9 Correct 149 ms 183984 KB Output is correct
10 Correct 234 ms 183820 KB Output is correct
11 Correct 171 ms 183848 KB Output is correct
12 Correct 2167 ms 183852 KB Output is correct
13 Correct 2091 ms 183884 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 142 ms 183804 KB Output is correct
16 Correct 224 ms 184168 KB Output is correct
17 Correct 147 ms 183928 KB Output is correct
18 Correct 141 ms 183860 KB Output is correct
19 Correct 192 ms 183964 KB Output is correct
20 Correct 323 ms 183840 KB Output is correct
21 Correct 360 ms 183876 KB Output is correct
22 Correct 736 ms 184040 KB Output is correct
23 Correct 163 ms 183848 KB Output is correct
24 Correct 447 ms 183864 KB Output is correct
25 Correct 106 ms 183464 KB Output is correct
26 Correct 171 ms 184208 KB Output is correct
27 Correct 145 ms 183880 KB Output is correct
28 Correct 142 ms 183792 KB Output is correct
29 Correct 189 ms 183956 KB Output is correct
30 Correct 212 ms 183772 KB Output is correct
31 Correct 220 ms 183244 KB Output is correct
32 Correct 326 ms 183808 KB Output is correct
33 Correct 587 ms 183628 KB Output is correct
34 Correct 990 ms 183504 KB Output is correct
35 Correct 1617 ms 183484 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 996 ms 1448428 KB Output is correct
3 Correct 928 ms 1450472 KB Output is correct
4 Correct 955 ms 1450564 KB Output is correct
5 Correct 1063 ms 1449932 KB Output is correct
6 Correct 1184 ms 1449864 KB Output is correct
7 Correct 1638 ms 1449660 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 189 ms 184248 KB Output is correct
10 Correct 173 ms 184300 KB Output is correct
11 Correct 132 ms 183920 KB Output is correct
12 Correct 135 ms 183900 KB Output is correct
13 Correct 197 ms 183884 KB Output is correct
14 Correct 313 ms 183868 KB Output is correct
15 Correct 199 ms 183832 KB Output is correct
16 Correct 149 ms 183984 KB Output is correct
17 Correct 234 ms 183820 KB Output is correct
18 Correct 171 ms 183848 KB Output is correct
19 Correct 2167 ms 183852 KB Output is correct
20 Correct 2091 ms 183884 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 142 ms 183804 KB Output is correct
23 Correct 224 ms 184168 KB Output is correct
24 Correct 147 ms 183928 KB Output is correct
25 Correct 141 ms 183860 KB Output is correct
26 Correct 192 ms 183964 KB Output is correct
27 Correct 323 ms 183840 KB Output is correct
28 Correct 360 ms 183876 KB Output is correct
29 Correct 736 ms 184040 KB Output is correct
30 Correct 163 ms 183848 KB Output is correct
31 Correct 447 ms 183864 KB Output is correct
32 Correct 106 ms 183464 KB Output is correct
33 Correct 171 ms 184208 KB Output is correct
34 Correct 145 ms 183880 KB Output is correct
35 Correct 142 ms 183792 KB Output is correct
36 Correct 189 ms 183956 KB Output is correct
37 Correct 212 ms 183772 KB Output is correct
38 Correct 220 ms 183244 KB Output is correct
39 Correct 326 ms 183808 KB Output is correct
40 Correct 587 ms 183628 KB Output is correct
41 Correct 990 ms 183504 KB Output is correct
42 Correct 1617 ms 183484 KB Output is correct
43 Correct 1 ms 1492 KB Output is correct
44 Correct 4 ms 5076 KB Output is correct
45 Correct 1089 ms 1449476 KB Output is correct
46 Correct 995 ms 1449256 KB Output is correct
47 Correct 931 ms 1449184 KB Output is correct
48 Correct 931 ms 1449064 KB Output is correct
49 Correct 1130 ms 1459276 KB Output is correct
50 Correct 940 ms 1456920 KB Output is correct
51 Correct 846 ms 1457440 KB Output is correct
52 Correct 953 ms 1454924 KB Output is correct
53 Correct 1877 ms 1455624 KB Output is correct
54 Correct 1737 ms 1456772 KB Output is correct
55 Correct 1980 ms 1455984 KB Output is correct
56 Correct 4123 ms 1456620 KB Output is correct
57 Correct 2873 ms 1456640 KB Output is correct
58 Correct 2794 ms 1456688 KB Output is correct
59 Correct 2514 ms 1456844 KB Output is correct
60 Correct 3584 ms 1455996 KB Output is correct
61 Correct 3577 ms 1455948 KB Output is correct