| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 826197 | TheSahib | 던전 (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 = 1e9 + 9;
const int MAX = 500005;
const int LOGMAX = 24;
const int startLog = 12;
int n;
vector<int> S, W, P, L;
struct G{
array<ll, 3> par[LOGMAX + 1][MAX];
void preCalc(){
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][m][2] + par[j - 1][i][1]);
}
}
}
pii lift(ll start, ll target, int v){
if(start >= target || v == n) return {v, start};
for(int j = LOGMAX; j >= 0 && v != n; --j){
ll a = start + par[j][v][1];
if(a < target && (start + par[j][v][2] < 0)){
start = a;
v = par[j][v][0];
}
}
if(v == n){
return {n, start};
}
if(start >= S[v]){
start += S[v];
v = W[v];
}
else{
start += P[v];
v = L[v];
}
return {v, start};
}
};
vector<ll> v;
G gs[LOGMAX - startLog + 1];
void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
n = N;
S = s;
P = p;
W = w;
L = l;
for(int i = startLog; i < LOGMAX; ++i){
v.push_back((1 << i));
}
for (int i = 0; i < v.size(); i++)
{
for(int j = 0; j <= N; ++j){
if(j == N){
gs[i].par[0][j] = {N, 0, -oo * oo};
continue;
}
if(s[j] > v[i]){
gs[i].par[0][j] = {l[j], p[j], p[j] - s[j]};
}
else{
gs[i].par[0][j] = {w[j], s[j], -oo * oo};
}
}
gs[i].preCalc();
}
v.push_back(oo * oo);
return;
}
ll simulate(int x, int z) {
ll u = x;
ll s = z;
while(s < (1 << startLog) && u != n){
if(s >= S[u]){
s += S[u];
u = W[u];
}
else{
s += P[u];
u = L[u];
}
}
for (int i = 0; i < v.size() - 1; i++)
{
while(s < v[i + 1] && u != n){
pii p = gs[i].lift(s, v[i + 1], u);
u = p.first;
s = p.second;
}
}
return s;
}