#include "dungeons.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 4e5 + 5;
const int M = 25;
vector<int> edges[N];
ll s[N], p[N], w[N], l[N], n;
ll pref[N], par[N][M], sum[N][M];
void dfs(int u){
//~ for(int j=1;j<20;j++){
//~ par[u][j] = par[par[u][j-1]][j-1];
//~ mx[u][j] = max(mx[u][j-1], mx[par[u][j-1]][j-1]);
//~ }
for(auto x : edges[u]){
pref[x] = pref[u] + s[x];
//~ par[x][0] = u, mx[x][0] = s[u] + pref[u];
dfs(x);
}
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> 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];
edges[w[i]].push_back(i);
par[i][0] = l[i];
sum[i][0] = p[i];
}
par[n][0] = n;
//~ par[n][0] = n;
dfs(n);
for(int j=1;j<M;j++){
for(int i=0;i<=n;i++){
par[i][j] = par[par[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[par[i][j-1]][j-1];
}
}
}
//~ ll go(int x, ll z){
//~ cout<<x<<" "<<z<<"\n";
//~ if(s[x] > z){
//~ return go(l[x], z + s[x]);
//~ }
//~ z += pref[x];
//~ for(int j=19;~j;j--){
//~ if(mx[x][j] <= z){
//~ x = par[x][j];
//~ }
//~ }
//~ x = par[x][0];
//~ if(x == n) return z;
//~ z -= pref[x];
//~ return go(l[x], z + s[x]);
//~ }
ll simulate(int x, int z) {
ll res = z;
for(int j=M-1;~j;j--){
if(res + sum[x][j] < s[0]){
res += sum[x][j];
x = par[x][j];
}
}
if(res >= s[0]){
return res + pref[x];
}
res += p[x];
x = l[x];
res += pref[x];
return res;
}
Compilation message
registers.cpp:1:10: fatal error: dungeons.h: No such file or directory
1 | #include "dungeons.h"
| ^~~~~~~~~~~~
compilation terminated.
