| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 531623 | 79brue | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll arr[400002], power[400002];
int w[400002], l[400002];
ll nxt[25][60002][25]; /// 계속 지기만 했을 때의 최종 위치
ll sum[25][60002][25]; /// 계속 지기만 했을 때의 체력 변화
ll lim[25][60002][25]; /// 계속 지기만 할 수 있기 위한 최초 체력의 최댓값
ll bonus[400002];
void init(int N, vector<int> s, vector<int> p, vector<int> W, vector<int> L){
n = N;
for(int i=0; i<n; i++) arr[i] = s[i];
for(int i=0; i<n; i++) power[i] = p[i], w[i]=W[i], l[i]=L[i];
l[n]=w[n]=n;
arr[n] = 1e18, power[n]=0;
for(int f=0; f<25; f++){
for(int i=0; i<=n; i++) nxt[f][i][0] = l[i], sum[f][i][0] = power[i], lim[f][i][0] = arr[i]-1;
for(int d=1; d<25; d++){
for(int i=0; i<=n; i++){
nxt[f][i][d] = nxt[f][nxt[f][i][d-1]][d-1];
sum[f][i][d] = sum[f][i][d-1] + sum[f][nxt[f][i][d-1]][d-1];
sum[f][i][d-1] = min(sum[f][i][d-1], 1e18);
lim[f][i][d] = min(lim[f][i][d-1], lim[f][nxt[f][i][d-1]][d-1] - sum[f][i][d-1]);
}
}
}
for(int i=n-1; i>=0; i--){
bonus[i] = arr[i] + bonus[w[i]];
}
}
ll simulate(int x, int _z){
ll z = _z;
for(int f=0; f<25; f++){
if((1<<(f+1)) <= z) continue;
/// 1. 계속 지다가 결국 탈출하기
ll minLeft = (1<<(f+1)) - z;
ll pSum = 0;
int tx = x, cnt1 = 0;
for(int d=24; d>=0; d--){
if(pSum + sum[f][tx][d] < minLeft){
pSum += sum[f][tx][d];
tx = nxt[f][tx][d];
cnt1 += (1<<d);
}
}
/// 2. 이겨서 탈출하기
int cnt2 = 0;
tx = x;
ll tz = z;
for(int d=24; d>=0; d--){
if(lim[f][tx][d] >= tz){
tz += sum[f][tx][d];
tx = nxt[f][tx][d];
cnt2 += (1<<d);
}
}
int cnt = min(cnt1, cnt2);
for(int d=0; d<25; d++){
if((cnt>>d)&1){
z += sum[f][x][d];
x = nxt[f][x][d];
}
}
if(z >= arr[x]) z += arr[x], x = w[x];
else z += power[x], x = l[x];
}
return z + bonus[x];
}