| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 609621 | FEDIKUS | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
typedef long long ll;
const int logz=9;
const int logn=25;
const int maxn=4e5+10;
struct{
ll gain,max;
int pos;
} lift[maxn][logz][logn];
int n;
vector<int> s,p;
vector<int> w,l;
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
n=nn; s=ss; p=pp; w=ww; l=ll;
s.resize(n+1); p.resize(n+1); w.resize(n+1), l.resize(n+1);
s[n]=0; p[n]=0; w[n]=n; l[n]=n;
for(int bit=0;bit<logz;bit++){
for(int jump=0;jump<logn;jump++){
for(int pos=0;pos<=n;pos++){
if(jump==0){
if((1<<bit*2)>=s[pos]) lift[pos][bit][jump]={s[pos],LLONG_MIN,w[pos]};
else lift[pos][bit][jump]={p[pos],-s[pos],l[pos]};
}else{
lift[pos][bit][jump]={lift[pos][bit][jump-1].gain+lift[lift[pos][bit][jump-1].pos][bit][jump-1].gain,
max(lift[pos][bit][jump-1].max,lift[pos][bit][jump-1].gain+lift[lift[pos][bit][jump-1].pos][bit][jump-1].max),
lift[lift[pos][bit][jump-1].pos][bit][jump-1].pos};
}
}
}
}
return;
}
int get_bit(ll a){
return min(63-__builtin_clzll(a),logz-1)/2;
}
long long simulate(int x, int z) {
long long res=z;
while(true){
if(res==0){
res=p[x];
x=l[x];
continue;
}
int bit=get_bit(res);
for(int jump=logn-1;jump>=0;jump--){
if(res+lift[x][bit][jump].max<0){
res+=lift[x][bit][jump].gain;
x=lift[x][bit][jump].pos;
}
}
if((1LL<<2*bit)<s[x] && res>=s[x]){
res+=s[x];
x=w[x];
}
if(x==n) break;
}
return res;
}