#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;
vector<int> edges[N];
ll s[N], p[N], w[N], l[N], n;
ll pref[N], par[N][20], mx[N][20];
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[n][0] = n;
dfs(n);
}
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) {
return go(x, z);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
10196 KB |
Output is correct |
2 |
Correct |
465 ms |
194188 KB |
Output is correct |
3 |
Correct |
488 ms |
214628 KB |
Output is correct |
4 |
Correct |
478 ms |
216104 KB |
Output is correct |
5 |
Correct |
494 ms |
178972 KB |
Output is correct |
6 |
Correct |
486 ms |
201176 KB |
Output is correct |
7 |
Correct |
409 ms |
212712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
10196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
10196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
10196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
10196 KB |
Output is correct |
2 |
Correct |
465 ms |
194188 KB |
Output is correct |
3 |
Correct |
488 ms |
214628 KB |
Output is correct |
4 |
Correct |
478 ms |
216104 KB |
Output is correct |
5 |
Correct |
494 ms |
178972 KB |
Output is correct |
6 |
Correct |
486 ms |
201176 KB |
Output is correct |
7 |
Correct |
409 ms |
212712 KB |
Output is correct |
8 |
Incorrect |
7 ms |
10196 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |