| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1011835 | boris_mihov | 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 "dungeons.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
typedef long long llong;
const int MAXN = 400000 + 10;
const int MAXNUMLOG = 25;
const llong INF = 4e18;
// const int MAXLOG = 16;
namespace
{
int n;
int h[MAXN];
int winNext[MAXN];
int loseNext[MAXN];
int loseGain[MAXN];
}
struct Sparse
{
int next[MAXNUMLOG][MAXN];
llong sumJumps[MAXNUMLOG][MAXN];
llong minimumZ[MAXNUMLOG][MAXN];
void build(int log)
{
memset(next, -1, sizeof(next));
for (int i = 0 ; i < n ; ++i)
{
if (h[i] <= (1 << log))
{
next[0][i] = winNext[i];
sumJumps[0][i] = h[i];
minimumZ[0][i] = INF;
} else
{
next[0][i] = loseNext[i];
sumJumps[0][i] = loseGain[i];
if (log == MAXNUMLOG - 1) minimumZ[0][i] = INF;
else minimumZ[0][i] = h[i];
}
}
next[0][n] = n;
sumJumps[0][n] = 0;
minimumZ[0][n] = 0;
for (int lg = 1 ; lg < MAXNUMLOG ; ++lg)
{
for (int i = 0 ; i <= n ; ++i)
{
next[lg][i] = next[lg - 1][next[lg - 1][i]];
sumJumps[lg][i] = sumJumps[lg - 1][i] + sumJumps[lg - 1][next[lg - 1][i]];
minimumZ[lg][i] = std::min(minimumZ[lg - 1][i], minimumZ[lg - 1][next[lg - 1][i]] - sumJumps[lg - 1][i]);
if (log == MAXNUMLOG - 1) minimumZ[lg][i] = INF;
}
}
}
void simulate(int &node, llong &z)
{
for (int lg = MAXNUMLOG - 1 ; lg >= 0 ; --lg)
{
assert(next[lg][node] != -1);
if (next[lg][node] == n || z >= minimumZ[lg][node])
{
continue;
}
z += sumJumps[lg][node];
node = next[lg][node];
}
if (z >= h[node])
{
z += h[node];
node = winNext[node];
} else
{
z += loseGain[node];
node = loseNext[node];
}
}
};
Sparse sparse[MAXNUMLOG];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
::n = n;
for (int i = 0 ; i < n ; ++i)
{
h[i] = s[i];
winNext[i] = w[i];
loseNext[i] = l[i];
loseGain[i] = p[i];
}
for (int i = 0 ; i < MAXNUMLOG ; ++i)
{
sparse[i].build(i);
}
return;
}
llong simulate(int X, int Z)
{
llong z = Z;
int node = X;
for (int i = 0 ; i < MAXNUMLOG ; ++i)
{
sparse[i].simulate(node, z);
if (node == n)
{
break;
}
}
return z;
}