| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1025980 | MinaRagy06 | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("Ofast")
int n;
const int N = 400'005;
const int LOG = 25, B = 8, LIFTS = 7; //LIFTS = log_B(1e7 + N)
const ll inf = 1e18;
struct node {
int anc;
ll strength, bound;
node() {}
node(int _anc, ll _strength, ll _bound) {
anc = _anc;
strength = _strength;
bound = _bound;
}
void operator+=(const node &r) {
//i -> l -> r
anc = r.anc;
bound = min(bound, r.bound - strength);
strength += r.strength;
}
};
vector<int> s, p, w, l;
node lift[N][LOG][LIFTS];
const int M = 1 << LOG;
int logs[M];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
logs[1] = 0;
for (int i = 2; i < M; i++) {
logs[i] = logs[i >> 1] + 1;
}
n = _n, s = _s, p = _p, w = _w, l = _l;
s.push_back(0), p.push_back(0), w.push_back(n), l.push_back(n);
for (int i = 0; i <= n; i++) {
for (int j = 0; j < LOG; j++) {
if (s[i] < (1 << j)) {
lift[i][j][0] = node(w[i], s[i], inf);
} else if (s[i] >= (1 << (j + 1))) {
lift[i][j][0] = node(l[i], p[i], inf);
} else { //log(s[i]) == log(z)
lift[i][j][0] = node(l[i], p[i], s[i] - 1);
}
}
}
for (int k = 1; k < LIFTS; k++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j < LOG; j++) {
lift[i][j][k] = lift[i][j][k - 1];
for (int o = 1; o < B; o++) {
lift[i][j][k] += lift[lift[i][j][k].anc][j][k - 1];
}
}
}
}
}
ll simulate(int x, int _z) {
ll z = _z;
while (x != n) {
if (z >= s[x]) {
z += s[x];
x = w[x];
} else{
z += p[x];
x = l[x];
}
int lg = (z < M? logs[z] : LOG - 1);
for (int k = LIFTS - 1; k >= 0; k--) {
for (int o = 1; o < B; o++) {
ll newz = z + lift[x][lg][k].strength;
if (z <= lift[x][lg][k].bound && (z >= (1 << (LOG - 1)) || (newz < M && logs[newz] == lg))) {
z += lift[x][lg][k].strength;
x = lift[x][lg][k].anc;
}
}
}
}
return z;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
ll st = chrono::steady_clock::now().time_since_epoch().count();
int _n;
cin >> _n;
vector<int> _s(_n), _p(_n), _w(_n), _l(_n);
for (int i = 0; i < _n; i++) cin >> _s[i];
for (int i = 0; i < _n; i++) cin >> _p[i];
for (int i = 0; i < _n; i++) cin >> _w[i];
for (int i = 0; i < _n; i++) cin >> _l[i];
init(_n, _s, _p, _w, _l);
int q;
cin >> q;
while (q--) {
int x, z;
cin >> x >> z;
cout << simulate(x, z) << '\n';
}
ll en = chrono::steady_clock::now().time_since_epoch().count();
// cout << (en - st) / 1e9 << "s\n";
return 0;
}