| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 609964 | Temmie | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
int n;
std::vector <int> s, p, w, l;
struct Index {
int dest;
long long plus;
long long consr;
} bin[25][20][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 < 25; b++) {
for (int i = 0; i < n; i++) {
if (s[i] < (1 << b)) {
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 < 25; b1++) {
for (int b2 = 1; b2 < 20; 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 < 25 && ans >= (1 << (b1 + 1))) {
b1++;
}
for (int b2 = 19; ~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;
}