| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 536445 | grt | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int nax = 50 * 1000 + 10, INF = 1e9 + 10;
int n;
ll sum[nax][17][25];
int jp[nax][17][25];
int lim[nax][17][25];
int s[nax], w[nax], l[nax], p[nax];
void init(int _n, vi _s, vi _p, vi _w, vi _l) {
n = _n;
for(int i = 0; i < n; ++i) {
s[i] = _s[i];
p[i] = _p[i];
w[i] = _w[i];
l[i] = _l[i];
}
w[n] = n; l[n] = n;
for(int bit = 0; (1 << bit) < 10'000'000; ++bit) {
for(int i = 0; i < n; ++i) {
if(_s[i] > (1 << bit)) {
jp[i][0][bit] = _l[i];
sum[i][0][bit] = _p[i];
lim[i][0][bit] = _s[i];
} else {
jp[i][0][bit] = _w[i];
sum[i][0][bit] = _s[i];
lim[i][0][bit] = INF;
}
}
jp[n][0][bit] = n;
lim[n][0][bit] = INF;
for(int j = 1; j < 17; ++j) {
for(int i = 0; i <= n; ++i) {
jp[i][j][bit] = jp[jp[i][j - 1][bit]][j - 1][bit];
sum[i][j][bit] = sum[jp[i][j - 1][bit]][j - 1][bit] + sum[i][j - 1][bit];
lim[i][j][bit] = min(lim[i][j - 1][bit], (int)max(0LL, (lim[jp[i][j - 1][bit]][j - 1][bit] - sum[i][j - 1][bit])));
}
}
}
}
ll simulate(int x, ll z) {
for(int bit = 0; bit < 25; ++bit) {
if((1 << (bit + 1)) > z) {
for(int i = 16; i >= 0; --i) {
if(lim[x][i][bit] >= z) {
z += sum[x][i][bit];
x = jp[x][i][bit];
}
}
if(z >= s[x]) {
z += s[x];
x = w[x];
} else {
z += p[x];
x = l[x];
}
}
}
return z;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
//cerr << simulate(0, 1) << "\n";
//cerr << simulate(2, 3) << "\n";
//}