| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 827616 | TahirAliyev | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, ll>
const ll oo = 1e18;
const int MAX = 400004, LOGMAX = 25;
const int logStart = 11;
int N;
vector<ll> S;
vector <int> st, P, W, L;
struct g{
array<ll, 3> par[LOGMAX][MAX];
void init(){
for (int j = 1; j < LOGMAX; j++)
{
for (int i = 0; i <= N; i++)
{
int m = par[j - 1][i][0];
par[j][i][0] = par[j - 1][m][0];
par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
par[j][i][2] = max(par[j - 1][i][2], par[j - 1][i][1] + par[j - 1][m][2]);
}
}
}
pii lift(int u, ll s, ll t){
if(u == N || s >= t){
return {u, s};
}
ll curs = s;
int v = u;
for (int j = LOGMAX - 1; j >= 0; j--)
{
if(curs + par[j][v][2] < 0){
curs += par[j][v][1];
v = par[j][v][0];
}
}
if(v == N) return {v, curs};
if(st[v] <= curs){
return make_pair(W[v], st[v] + curs);
}
else{
return make_pair(L[v], P[v] + curs);
}
}
};
g G[LOGMAX - logStart];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = n;
st = s;
P = p;
W = w;
L = l;
for (int i = logStart; i < LOGMAX; i += 2)
{
S.push_back(1ll << i);
}
for (int j = 0; j < S.size(); j++)
{
for (int i = 0; i < n; i++)
{
if(s[i] <= S[j]){
G[j].par[0][i] = {w[i], s[i], -oo};
}
else{
G[j].par[0][i] = {l[i], p[i], -s[i]};
}
}
}
S.push_back(oo);
for (int j = 0; j < S.size(); j++)
{
G[j].par[0][n] = {n, 0, -oo};
G[j].init();
}
}
ll simulate(int x, int z) {
ll X = x, Z = z;
while(Z < (1 << logStart) && X != N){
if(Z >= st[X]){
Z += st[X];
X = W[X];
}
else{
Z += P[X];
X = L[X];
}
}
for (int i = 0; i < S.size() - 1; i++)
{
while(Z < S[i + 1] && X != N){
pii a = G[i].lift(X, Z, S[i + 1]);
X = a.first, Z = a.second;
}
}
return Z;
}