| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 551306 | topovik | 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>
#define pb push_back
#define f first
#define s second
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll oo = 1e18;
const ld eps = (ld)1 / oo;
const ll N = 4e5+ 1;
const ll M = 25;
vector <int> s, p, w, l;
int n;
ll sum[M][N][M];
ll mx[M][N][M];
int nx[M][N][M];
void init(int n1, vector <int> s1, vector <int> p1, vector <int> w1, vector <int> l1)
{
n = n1;
s = s1, p = p1, w = w1, l = l1;
for (int pw = 0; pw < M; pw++)
{
for (int i = 0; i < n; i++)
if (s[i] < (1ll << pw))
{
nx[pw][i][0] = w[i];
mx[pw][i][0] = -oo;
sum[pw][i][0] = s[i];
}
else
{
nx[pw][i][0] = l[i];
mx[pw][i][0] = -s[i];
sum[pw][i][0] = p[i];
}
nx[pw][n][0] = n;
mx[pw][n][0] = -oo;
sum[pw][n][0] = 0;
for (int j = 1; j < M; j++)
{
for (int i = 0; i <= n; i++)
{
int c = nx[pw][i][j - 1];
nx[pw][i][j] = nx[pw][c][j - 1];
mx[pw][i][j] = max(mx[pw][i][j - 1], mx[pw][c][j - 1] + sum[pw][i][j - 1]);
sum[pw][i][j] = sum[pw][i][j - 1] + sum[pw][c][j - 1];
}
}
}
}
ll simulate(int x, int y1)
{
ll y = y1;
for (int i = 0; i < M; i++)
if (((1ll << i) <= y && (1ll << (i + 1)) > y) || i == M - 1)
{
for (int j = M - 1; j >= 0; j--)
if (mx[i][x][j] + y < 0) y += sum[i][x][j], x = nx[i][x][j];
if (x == n) return y;
y += s[x];
x = w[x];
}
return y;
}
//int main()
//{
// srand(time(NULL));
// ll n, q;
// cin >> n >> q;
// vector <int> a(n), b(n), c(n), d(n);
// for (ll i = 0; i < n; i++) cin >> a[i];
// for (ll i = 0; i < n; i++) cin >> b[i];
// for (ll i = 0; i < n; i++) cin >> c[i];
// for (ll i = 0; i < n; i++) cin >> d[i];
// init(n, a, b, c, d);
// while (q--)
// {
// ll x, z;
// cin >> x >> z;
// cout << simulate(x, z) << endl;
// }
//}