| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 599486 | definitelynotmee | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>;
const int T = 1;
struct jmp{
ll to, plus, win;
jmp merge(jmp b){
jmp ret;
ret.to = b.to;
ret.plus = plus+b.plus;
ret.win = min(win,b.win-plus);
return ret;
}
};
jmp lift[24][24][50000];
matrix<jmp> lift2;
vector<ll> windp;
int N;
vector<int> S, P, W, L;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
S =s;
P = p;
W = w;
L = l;
int t = T;
if(n > 5e4){
lift2 = matrix<jmp>(int(log2(T)+1),vector<jmp>(n));
for(int i = 0; i < n; i++){
if(s[i] <= T){
lift2[0][i] = {w[i],s[i],1ll<<60};
if(w[i] == n){
lift2[0][i].win = 0, lift2[0][i].to = i;
}
} else {lift2[0][i] = {l[i],p[i],s[i]};
if(l[i] == n)
lift2[0][i].win = 0, lift2[0][i].to = i;
}
}
for(int i = 1; i < lift2.size(); i++){
for(int j = 0; j < n; j++)
lift2[i][j] = lift2[i-1][j].merge(lift2[i-1][lift2[i-1][j].to]);
}
} else {
for(int x = 0; x < 24; x++){
for(int i = 0; i < n; i++){
if(s[i] <= t){
lift[x][0][i] = {w[i],s[i],1ll<<60};
if(w[i] == n){
lift[x][0][i].win = 0, lift[x][0][i].to = i;
}
} else {lift[x][0][i] = {l[i],p[i],s[i]};
if(l[i] == n)
lift[x][0][i].win = 0, lift[x][0][i].to = i;
}
}
for(int i = 1; i < 24; i++){
for(int j = 0; j < n; j++)
lift[x][i][j] = lift[x][i-1][j].merge(lift[x][i-1][lift[x][i-1][j].to]);
}
t*=2;
}
}
windp = vector<ll>(n+1);
for(int i = n-1; i >= 0; i--)
windp[i] = windp[w[i]]+s[i];
return;
}
long long simulate(int x, int Z) {
ll z = Z;
int it = T;
while(it-- && x != N){
if(S[x] <= z){
z+=S[x];
x=W[x];
} else {
z+=P[x];
x=L[x];
}
}
if(n > 5e4){
while(x!=N && z < int(1e7)){
for(int i = int(lift2.size())-1; i>= 0; i--){
if(lift2[i][x].win > z){
z+=lift2[i][x].plus;
x = lift2[i][x].to;
}
}
if(S[x] <= z){
z+=S[x];
x=W[x];
} else {
z+=P[x];
x=L[x];
}
}
} else {
int power = 0;
while(x!=N && z < int(1e7)){
while(z >= T*(1<<power+1) && power < 23)
power++;
for(int i = 23; i>= 0; i--){
if(lift[power][i][x].win > z){
z+=lift[power][i][x].plus;
x = lift[power][i][x].to;
}
}
if(S[x] <= z){
z+=S[x];
x=W[x];
} else {
z+=P[x];
x=L[x];
}
}
}
return z+windp[x];
}