# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
794682 | 2023-07-26T19:01:28 Z | finn__ | Dungeons Game (IOI21_dungeons) | C++17 | 7000 ms | 1423128 KB |
#include <bits/stdc++.h> #include "dungeons.h" using namespace std; constexpr size_t N = 400001, K = 25, L = 9; size_t n; uint32_t f[L][K][N], m[L][K][N]; uint64_t u[L][K][N]; vector<int> s, p, w, l; void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) { n = n_; s = move(s_); p = move(p_); w = move(w_); l = move(l_); for (size_t k = 0; k < L; ++k) { for (size_t i = 0; i < n; ++i) { if (s[i] < 1ULL << (k * 3)) f[k][0][i] = w[i], u[k][0][i] = s[i], m[k][0][i] = UINT32_MAX; else f[k][0][i] = l[i], u[k][0][i] = p[i], m[k][0][i] = s[i]; } f[k][0][n] = n; u[k][0][n] = 0; m[k][0][n] = UINT32_MAX; for (size_t j = 1; j < K; ++j) for (size_t i = 0; i < n; ++i) { size_t const intermediate = f[k][j - 1][i]; f[k][j][i] = f[k][j - 1][intermediate]; u[k][j][i] = u[k][j - 1][i] + u[k][j - 1][intermediate]; m[k][j][i] = m[k][j - 1][i]; if (m[k][j - 1][intermediate] != UINT32_MAX) { uint32_t v = m[k][j - 1][intermediate] - min<uint64_t>(m[k][j - 1][intermediate], u[k][j - 1][i]); m[k][j][i] = min(m[k][j][i], v); } } } } long long simulate(int x, int z) { long long strength = z; while (x != n) { if (strength >= s[x]) { strength += s[x]; x = w[x]; } else { strength += p[x]; x = l[x]; } size_t const k = min<size_t>(L - 1, __lg(strength) / 3); for (size_t j = K - 1; j < K; --j) if (m[k][j][x] > strength) { strength += u[k][j][x]; x = f[k][j][x]; break; } } return strength; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5204 KB | Output is correct |
2 | Correct | 2 ms | 5204 KB | Output is correct |
3 | Correct | 6 ms | 12244 KB | Output is correct |
4 | Correct | 117 ms | 182732 KB | Output is correct |
5 | Correct | 9 ms | 12244 KB | Output is correct |
6 | Correct | 113 ms | 182660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8788 KB | Output is correct |
2 | Correct | 909 ms | 1423004 KB | Output is correct |
3 | Correct | 836 ms | 1422956 KB | Output is correct |
4 | Correct | 858 ms | 1423004 KB | Output is correct |
5 | Correct | 867 ms | 1423024 KB | Output is correct |
6 | Correct | 925 ms | 1423052 KB | Output is correct |
7 | Correct | 900 ms | 1423052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8788 KB | Output is correct |
2 | Correct | 147 ms | 184016 KB | Output is correct |
3 | Correct | 5055 ms | 184072 KB | Output is correct |
4 | Correct | 132 ms | 183944 KB | Output is correct |
5 | Correct | 132 ms | 183896 KB | Output is correct |
6 | Correct | 183 ms | 184012 KB | Output is correct |
7 | Correct | 176 ms | 183904 KB | Output is correct |
8 | Correct | 160 ms | 183884 KB | Output is correct |
9 | Correct | 138 ms | 183808 KB | Output is correct |
10 | Correct | 161 ms | 183884 KB | Output is correct |
11 | Correct | 184 ms | 183764 KB | Output is correct |
12 | Correct | 235 ms | 184108 KB | Output is correct |
13 | Correct | 172 ms | 183900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8788 KB | Output is correct |
2 | Correct | 147 ms | 184016 KB | Output is correct |
3 | Correct | 5055 ms | 184072 KB | Output is correct |
4 | Correct | 132 ms | 183944 KB | Output is correct |
5 | Correct | 132 ms | 183896 KB | Output is correct |
6 | Correct | 183 ms | 184012 KB | Output is correct |
7 | Correct | 176 ms | 183904 KB | Output is correct |
8 | Correct | 160 ms | 183884 KB | Output is correct |
9 | Correct | 138 ms | 183808 KB | Output is correct |
10 | Correct | 161 ms | 183884 KB | Output is correct |
11 | Correct | 184 ms | 183764 KB | Output is correct |
12 | Correct | 235 ms | 184108 KB | Output is correct |
13 | Correct | 172 ms | 183900 KB | Output is correct |
14 | Correct | 4 ms | 8788 KB | Output is correct |
15 | Correct | 136 ms | 183972 KB | Output is correct |
16 | Correct | 141 ms | 184012 KB | Output is correct |
17 | Correct | 134 ms | 183884 KB | Output is correct |
18 | Correct | 134 ms | 183988 KB | Output is correct |
19 | Correct | 186 ms | 183956 KB | Output is correct |
20 | Correct | 162 ms | 183916 KB | Output is correct |
21 | Correct | 169 ms | 183944 KB | Output is correct |
22 | Correct | 168 ms | 183828 KB | Output is correct |
23 | Correct | 222 ms | 183884 KB | Output is correct |
24 | Correct | 263 ms | 183944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8788 KB | Output is correct |
2 | Correct | 147 ms | 184016 KB | Output is correct |
3 | Correct | 5055 ms | 184072 KB | Output is correct |
4 | Correct | 132 ms | 183944 KB | Output is correct |
5 | Correct | 132 ms | 183896 KB | Output is correct |
6 | Correct | 183 ms | 184012 KB | Output is correct |
7 | Correct | 176 ms | 183904 KB | Output is correct |
8 | Correct | 160 ms | 183884 KB | Output is correct |
9 | Correct | 138 ms | 183808 KB | Output is correct |
10 | Correct | 161 ms | 183884 KB | Output is correct |
11 | Correct | 184 ms | 183764 KB | Output is correct |
12 | Correct | 235 ms | 184108 KB | Output is correct |
13 | Correct | 172 ms | 183900 KB | Output is correct |
14 | Correct | 4 ms | 8788 KB | Output is correct |
15 | Correct | 136 ms | 183972 KB | Output is correct |
16 | Correct | 141 ms | 184012 KB | Output is correct |
17 | Correct | 134 ms | 183884 KB | Output is correct |
18 | Correct | 134 ms | 183988 KB | Output is correct |
19 | Correct | 186 ms | 183956 KB | Output is correct |
20 | Correct | 162 ms | 183916 KB | Output is correct |
21 | Correct | 169 ms | 183944 KB | Output is correct |
22 | Correct | 168 ms | 183828 KB | Output is correct |
23 | Correct | 222 ms | 183884 KB | Output is correct |
24 | Correct | 263 ms | 183944 KB | Output is correct |
25 | Correct | 112 ms | 182688 KB | Output is correct |
26 | Correct | 145 ms | 183948 KB | Output is correct |
27 | Correct | 138 ms | 183912 KB | Output is correct |
28 | Correct | 137 ms | 183900 KB | Output is correct |
29 | Correct | 149 ms | 183948 KB | Output is correct |
30 | Correct | 185 ms | 183932 KB | Output is correct |
31 | Correct | 198 ms | 183904 KB | Output is correct |
32 | Correct | 339 ms | 183928 KB | Output is correct |
33 | Correct | 812 ms | 184024 KB | Output is correct |
34 | Correct | 1492 ms | 184024 KB | Output is correct |
35 | Correct | 651 ms | 184068 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8788 KB | Output is correct |
2 | Correct | 909 ms | 1423004 KB | Output is correct |
3 | Correct | 836 ms | 1422956 KB | Output is correct |
4 | Correct | 858 ms | 1423004 KB | Output is correct |
5 | Correct | 867 ms | 1423024 KB | Output is correct |
6 | Correct | 925 ms | 1423052 KB | Output is correct |
7 | Correct | 900 ms | 1423052 KB | Output is correct |
8 | Correct | 4 ms | 8788 KB | Output is correct |
9 | Correct | 147 ms | 184016 KB | Output is correct |
10 | Correct | 5055 ms | 184072 KB | Output is correct |
11 | Correct | 132 ms | 183944 KB | Output is correct |
12 | Correct | 132 ms | 183896 KB | Output is correct |
13 | Correct | 183 ms | 184012 KB | Output is correct |
14 | Correct | 176 ms | 183904 KB | Output is correct |
15 | Correct | 160 ms | 183884 KB | Output is correct |
16 | Correct | 138 ms | 183808 KB | Output is correct |
17 | Correct | 161 ms | 183884 KB | Output is correct |
18 | Correct | 184 ms | 183764 KB | Output is correct |
19 | Correct | 235 ms | 184108 KB | Output is correct |
20 | Correct | 172 ms | 183900 KB | Output is correct |
21 | Correct | 4 ms | 8788 KB | Output is correct |
22 | Correct | 136 ms | 183972 KB | Output is correct |
23 | Correct | 141 ms | 184012 KB | Output is correct |
24 | Correct | 134 ms | 183884 KB | Output is correct |
25 | Correct | 134 ms | 183988 KB | Output is correct |
26 | Correct | 186 ms | 183956 KB | Output is correct |
27 | Correct | 162 ms | 183916 KB | Output is correct |
28 | Correct | 169 ms | 183944 KB | Output is correct |
29 | Correct | 168 ms | 183828 KB | Output is correct |
30 | Correct | 222 ms | 183884 KB | Output is correct |
31 | Correct | 263 ms | 183944 KB | Output is correct |
32 | Correct | 112 ms | 182688 KB | Output is correct |
33 | Correct | 145 ms | 183948 KB | Output is correct |
34 | Correct | 138 ms | 183912 KB | Output is correct |
35 | Correct | 137 ms | 183900 KB | Output is correct |
36 | Correct | 149 ms | 183948 KB | Output is correct |
37 | Correct | 185 ms | 183932 KB | Output is correct |
38 | Correct | 198 ms | 183904 KB | Output is correct |
39 | Correct | 339 ms | 183928 KB | Output is correct |
40 | Correct | 812 ms | 184024 KB | Output is correct |
41 | Correct | 1492 ms | 184024 KB | Output is correct |
42 | Correct | 651 ms | 184068 KB | Output is correct |
43 | Correct | 2 ms | 5204 KB | Output is correct |
44 | Correct | 5 ms | 8788 KB | Output is correct |
45 | Correct | 1014 ms | 1423000 KB | Output is correct |
46 | Correct | 834 ms | 1423128 KB | Output is correct |
47 | Correct | 843 ms | 1422988 KB | Output is correct |
48 | Execution timed out | 7112 ms | 1422616 KB | Time limit exceeded |
49 | Halted | 0 ms | 0 KB | - |