| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1026017 | MinaRagy06 | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, L = 3, B = 1 << 3, 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];
node cur[N][L - 1];
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 j = 0; j < LOG; j++) {
for (int i = 0; i <= n; i++) {
cur[i][0] = lift[i][j][k - 1];
cur[i][0] += lift[cur[i][0].anc][j][k - 1];
}
for (int o = 1; o < L - 1; o++) {
for (int i = 0; i <= n; i++) {
cur[i][o] = cur[i][o - 1];
cur[i][o] += cur[cur[i][o].anc][o - 1];
}
}
for (int i = 0; i <= n; i++) {
lift[i][j][k] = cur[i][L - 2];
lift[i][j][k] += cur[lift[i][j][k].anc][L - 2];
}
}
}
}
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;
}