| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 566382 | kartel | 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>
//#include "grader.cpp"
#include "dungeons.h"
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("-Ofast")
using namespace std;
typedef long long ll;
const int N = 4e5 + 500;
const int log2A = 24;
const int log2N = 20;
int up[N][log2N][log2A];
ll sum[N][log2N][log2A];
ll dp[N][log2N][log2A];
int n;
void init(int _n, vector <int> s, vector <int> p, vector <int> w, vector <int> l) {
n = _n;
for (int k = 0; k < log2N; k++) {
for (int i = 0; i < n; i++) {
if (s[i] < (1 << k)) {
up[i][0][k] = w[i];
sum[i][0][k] = s[i];
dp[i][0][k] = -1e18;
} else {
up[i][0][k] = l[i];
sum[i][0][k] = p[i];
dp[i][0][k] = -s[i];
}
}
for (int st = 1; st < log2N; st++) {
for (int i = 0; i < n; i++) {
up[i][st][k] = up[i][st - 1][k];
sum[i][st][k] = sum[i][st - 1][k];
dp[i][st][k] = dp[i][st - 1][k];
for (int j = 1; j < 2; j++) {
dp[i][st][k] = max(dp[i][st][k], dp[up[i][st][k]][st - 1][k] + sum[i][st][k]);
sum[i][st][k] += sum[up[i][st][k]][st - 1][k];
up[i][st][k] = up[up[i][st][k]][st - 1][k];
}
}
}
}
}
ll simulate(int x, int start) {
ll z = start;
for (int k = 0; k < log2N; k++) {
if (z >= (1ll << (k + 1))) {
continue;
}
for (int j = log2N - 1; j >= 0; j--) {
for (int p = 0; p < 2; p++) {
if (z + dp[x][j][k] < 0) {
z += sum[x][j][k];
x = up[x][j][k];
} else {
break;
}
}
}
}
return z;
}
/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
*/