| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 467219 | blue | 던전 (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 <vector>
#include <cassert>
#include <iostream>
using namespace std;
const int maxN = 400'000;
const int logN = 20;
const int logS = 27;
int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;
long long nxt[1+maxN][logS][logN];
long long gain[1+maxN][logS][logN];
long long min_change[1+maxN][logS][logN]; //i, k, e
const int logMX = 50;
long long pow2[1+logMX];
vector<long long> winscore(1+maxN, 0LL);
void tle_assert(bool b)
{
if(!b) while(1);
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
N = n;
S = s;
P = p;
W = w;
L = l;
pow2[0] = 1;
for(int e = 1; e <= logMX; e++)
pow2[e] = 2 * pow2[e-1];
for(int i = 0; i <= N; i++)
{
for(int k = 0; k < logS; k++)
{
if(s[i] < pow2[k])
{
nxt[i][k][0] = w[i];
gain[i][k][0] = s[i];
min_change[i][k][0] = pow2[k+1] - gain[i][k][0];
}
else if(pow2[k] <= s[i] && s[i] < pow2[k+1])
{
nxt[i][k][0] = l[i];
gain[i][k][0] = p[i];
min_change[i][k][0] = min(pow2[k+1] - p[i], (long long)s[i]);
}
else if(pow2[k] < s[i])
{
nxt[i][k][0] = l[i];
gain[i][k][0] = p[i];
min_change[i][k][0] = pow2[k+1] - gain[i][k][0];
}
}
}
for(int e = 1; e < logN; e++)
{
for(int i = 0; i <= N; i++)
{
for(int k = 0; k < logS; k++)
{
nxt[i][k][e] = nxt[ nxt[i][k][e-1] ][k][e-1];
gain[i][k][e] = gain[i][k][e-1] + gain[ nxt[i][k][e-1] ][k][e-1];
min_change[i][k][e] = min(min_change[i][k][e-1], min_change[ nxt[i][k][e-1] ][k][e-1] - gain[i][k][e-1]);
}
}
}
for(int i = N-1; i >= 0; i--)
winscore[i] = winscore[ W[i] ] + S[i];
// for(int i = 0; i <= N; i++) cerr << winscore[i] << ' ';
// cerr << '\n';
// for(int k = 0; k < logS; k++)
// {
// for(int e = 0; e < logN; e++)
// {
// cerr << nxt[N][k][e] << ' ';
//
// }
// cerr << '\n';
// }
// cerr << '\n';
}
long long simulate(int x, int z)
{
// cerr << "\n\n\n\n";
// cerr << "simulating " << x << ' ' << z << '\n';
int X = x;
long long Z = z;
for(int k = 0; k < logS; k++)
{
if(pow2[k+1] <= Z) continue;
// cerr << "\n";
// cerr << k << ' ' << X << ' ' << Z << '\n';
// cerr << k << ' ' << pow2[k] << ' ' << Z << '\n';
// tle_assert(pow2[k] <= Z); //THIS IS FAILING!!!!
// tle_assert(Z < pow2[k+1]);
for(int e = logN - 1; e >= 0; e--)
{
if(Z >= min_change[X][k][e]) continue;
Z += gain[X][k][e];
X = nxt[X][k][e];
if(X == N) break;
}
if(X == N) break;
// cerr << "N = " << N << '\n';
// cerr << "initial Z = " << Z << '\n';
if(Z >= S[X])
{
Z += S[X];
X = W[X];
}
else
{
Z += P[X];
X = L[X];
}
if(X == N) break;
// cerr << "Z = " << Z << '\n';
assert(pow2[k+1] <= Z);
}
// cerr << "Z = " << Z << '\n';
// cerr << "ending X = " << X << '\n';
Z += winscore[X];
return Z;
}