| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 815302 | eltu0815 | 던전 (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;
const int MX = 5;
int pos[MX][400001][25];
ll mn[MX][400001][25], sum[MX][400001][25];
ll dp[400001];
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;
for(int j = 0; j < MX; ++j) {
for(int i = 0; i < N; ++i) {
pos[j][i][0] = (1 << 3 * j) <= S[i] ? L[i] : W[i];
sum[j][i][0] = (1 << 3 * j) <= S[i] ? P[i] : S[i];
mn[j][i][0] = (1 << 3 * j) <= S[i] ? S[i] : (ll)(1e16);
}
pos[j][N][0] = N, sum[j][N][0] = 0;
}
for(int k = 0; k < MX; ++k) for(int j = 1; j < 25; ++j) {
for(int i = 0; i <= N; ++i) {
pos[k][i][j] = pos[k][pos[k][i][j - 1]][j - 1];
sum[k][i][j] = sum[k][pos[k][i][j - 1]][j - 1] + sum[k][i][j - 1];
mn[k][i][j] = min(mn[k][i][j - 1], mn[k][pos[k][i][j - 1]][j - 1] - sum[k][i][j - 1]);
}
}
for(int i = n - 1; i >= 0; --i) dp[i] = dp[W[i]] + S[i];
return;
}
long long simulate(int x, int z) {
ll ans = z;
for(int k = 0; k < MX; ++k) {
while(ans < (1ll << 3 * k + 3)) {
for(int j = 24; j >= 0; --j) {
if(pos[k][x][j] != N && sum[k][x][j] + ans < (1 << 3 * k + 3) && mn[k][x][j] > ans) {
ans += sum[k][x][j], x = pos[k][x][j];
}
}
if(s[x] > ans && x != n && ans < (1 << 3 * k + 3)) ans += p[x], x = l[x];
if(x == N) return ans;
if(s[x] <= ans) ans += s[x], x = w[x];
if(x == N) return ans;
}
}
return ans + dp[x];
}