| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 830057 | fatemetmhr | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Be Name Khoda //
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
const int maxn5 = 4e5 + 5;//4e2 + 5;
const int lgr = 25;
const int lgl = 10;
int n, par[lgr - lgl + 1][lgr][maxn5];
int s[maxn5], p[maxn5], w[maxn5], l[maxn5];
ll val[lgr - lgl + 1][lgr][maxn5];
int mn[lgr - lgl + 1][lgr][maxn5];
int get_lev(ll x){
return 63 - __builtin_clzll(x);
}
void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
n = nn;
for(int i = 0; i < n; i++){
s[i] = ss[i];
p[i] = pp[i];
w[i] = ww[i];
l[i] = ll[i];
}
memset(par, -1, sizeof par);
for(int x = 0; x < lgr - lgl; x++){
for(int i = 0; i < n; i++){
int re = ((1 << (x + lgl)) >= s[i]);
par[x][0][i] = re ? w[i] : l[i];
val[x][0][i] = re ? s[i] : p[i];
mn[x][0][i] = re ? -1 : s[i];
}
for(int k = 1; k < lgr; k++)
for(int i = 0; i < n; i++) if(par[x][k - 1][i] != -1){
int v = par[x][k - 1][i];
par[x][k][i] = par[x][k - 1][v];
val[x][k][i] = val[x][k - 1][i] + val[x][k - 1][v];
mn[x][k][i] = mn[x][k - 1][i];
if(mn[x][k - 1][v] != -1 && (mn[x][k - 1][i] == -1 || mn[x][k - 1][v] - val[x][k - 1][i] < mn[x][k][i]))
mn[x][k][i] = max(0ll, mn[x][k - 1][v] - val[x][k - 1][i]);
}
}
return;
}
long long simulate(int x, int zz) {
ll ret = zz;
while(ret < (1 << lgl) && x < n){
bool re = ret >= s[x];
ret += (re ? s[x] : p[x]);
x = (re ? w[x] : l[x]);
}
int last = -1;
while(x < n){
int lev = get_lev(ret);
lev = min(lev, lgr - 1);
if(lev < lgr - 1 && lev == last && false)
exit(0);
last = lev;
//debug("*******");
//debug(lev);
//debug(x);
//debug(ret);
lev -= lgl;
for(int i = lgr - 1; i >= 0; i--){
//debug(i);
//debug(x);
//debug(ret);
//debug(mn[lev][i][x]);
//debug(par[lev][i][x]);
if(par[lev][i][x] != -1 && (mn[lev][i][x] == -1 || mn[lev][i][x] > ret)){
ret += val[lev][i][x];
x = par[lev][i][x];
}
}
if(x == n)
return ret;
//debug("here");
//debug(x);
//debug(ret);
//debug(s[x]);
//debug(mn[lev][0][x]);
//debug(w[x]);
//debug(l[x]);
if(s[x] <= (1 << (lev + lgl)))
return -1;
bool re = ret >= s[x];
if(!re && false)
exit(0);
ret += (re ? s[x] : p[x]);
x = (re ? w[x] : l[x]);
}
return ret;
}