| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 612521 | AmirElarbi | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9;
const int nax = 4e5+5;
const int lg = 25;
#include "dungeons.h"
ll nxt[8][nax][lg], sm[8][nax][lg], mn[8][nax][lg], n;
vi s,p,w,l;
void init(int N, vi S, vi P, vi W, vi L) {
n = N;
s = S, p = P, w = W, l = L;
s.pb(0);
p.pb(0);
for (int i = 0; i < lg; ++i)
{
for(int j =0; j < 8; j++) nxt[j][n][i] = n, sm[j][n][i] = 0, mn[j][n][i] = 1e9;
}
ll cur = 1;
for(int ind = 0; ind < 8; ind++){
for (int i = n-1; i >= 0; --i)
{
if(cur >= s[i]) nxt[ind][i][0] = w[i], sm[ind][i][0] = s[i], mn[ind][i][0] = min(s[w[i]],s[i]);
else nxt[ind][i][0] = l[i], sm[ind][i][0] = p[i], mn[ind][i][0] = min(p[l[i]],p[i]);
for (int j = 1; j < lg; ++j)
{
nxt[ind][i][j] = nxt[ind][nxt[ind][i][j-1]][j-1];
sm[ind][i][j] = sm[ind][i][j-1] + sm[ind][nxt[ind][i][j-1]][j-1];
mn[ind][i][j] = min(mn[ind][i][j-1], mn[ind][nxt[ind][i][j-1]][j-1]);
}
}
cur *= 10;
}
}
long long simulate(int x, ll z) {
ll ind = 0, cur = 1;
while(x != n){
while(ind < 7 && 10*cur <= z) ind++, cur *= 10;
for (int i = 0; i < lg; ++i)
{
if(z < mn[ind][x][i]){
z += sm[ind][x][i];
x = nxt[ind][x][i];
}
}
if(z >= s[x]) z += s[x], x = w[x];
else z += p[x], x = l[x];
}
return z;
}