| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 618839 | Tekor | 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 "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define en '\n'
const int N = 4e5 + 10;
const ll LLINF = (ll)2e9;
int up[N][26][26],k,w[N],l[N],mn[N][26][26];
ll sum[N][26][26],a[N],s[N],p[N],st[N];
vector <ll> tek;
/*
3 2
6 6 6
3 1 2
2 2 3
1 0 1
0 1
2 3
*/
void init(int n,vector <int> S,vector <int> P,vector <int> W,vector <int> L) {
st[n] = 0;
k = n;
st[0] = 1;
up[n][0][0] = n;
for(int i = 1;i <= 25;i++) {
st[i] = st[i - 1] * 2ll;
for(int j = 0;j <= 25;j++) {
up[n][i][j] = n;
}
up[n][0][i] = n;
}
for(int i = n - 1;i >= 0;i--) {
s[i] = S[i];
p[i] = P[i];
w[i] = W[i];
l[i] = L[i];
a[i] = s[i];
}
for(int i = 0;i <= 25;i++) {
for(int h = 0;h < n;h++) {
if(i > 0 && a[h] <= st[i - 1]) {
up[h][i][0] = w[h];
sum[h][i][0] = s[h];
if((i == 0 || a[w[h]] > st[i - 1])) {
mn[h][i][0] = a[w[h]] - s[h];
}else {
mn[h][i][0] = LLINF;
}
}else {
up[h][i][0] = l[h];
sum[h][i][0] = p[h];
if((i == 0 || a[l[h]] > st[i - 1])) {
mn[h][i][0] = a[l[h]] - p[h];
}else {
mn[h][i][0] = LLINF;
}
}
}
for(int j = 1;j <= 25;j++) {
for(int h = 0;h < n;h++) {
up[h][i][j] = up[up[h][i][j - 1]][i][j - 1];
sum[h][i][j] = sum[h][i][j - 1] + sum[up[h][i][j - 1]][i][j - 1];
mn[h][i][j] = min(mn[h][i][j - 1],mn[up[h][i][j - 1]][i][j - 1] - (int)sum[h][i][j - 1]);
}
}
}
}
pair <int,ll> check(int v,ll val,int it) {
if(val >= tek[it] || v == k)return mp(v,val);
for(int i = 26;i >= 0;i--) {
if(sum[v][it][i] + val < tek[it] && up[v][it][i] != k) {
val += sum[v][it][i];
v = up[v][it][i];
}
}
val += sum[v][it][0];
v = up[v][it][0];
return mp(v,val);
}
ll dfs(int v,ll val) {
if(v == k)return val;
if(val >= s[v])return dfs(w[v],val + s[v]);
else return dfs(l[v],val + p[v]);
}
ll simulate(int v,int z) {
ll val = z;
while(v != k) {
int pp = 25;
for(int i = 0;i <= 25;i++) {
if(st[i] > val) {
pp = i;
break;
}
}
if(pp > 0 && a[v] > st[pp - 1] && a[v] <= val) {
val += a[v];
v = w[v];
continue;
}
for(int i = 25;i >= 0;i--) {
if(up[v][pp][i] != k && mn[v][pp][i] > val) {
val += sum[v][pp][i];
v = up[v][pp][i];
}
}
val += sum[v][pp][0];
v = up[v][pp][0];
//cout << v << " " << val << " " << pp << en;
}
return val;
}