#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 4e5 + 3;
int n;
vector<int>s, p, w, l;
int nxtBig[nax];
long long sum_toNext[nax], sum_toN[nax];
vector<int>g[nax];
set<pair<int,int>> dfs(int v, long long sum = 0) {
if(v < n) sum += s[v];
sum_toN[v] = sum;
set<pair<int,int>>me;
for(int u : g[v]) {
auto he = dfs(u, sum);
if(me.size()<he.size()) me.swap(he);
for(auto e : he) me.insert(e);
}
while(!me.empty()) {
auto [val, he] = *me.begin();
if(v < n && val >= s[v]) break;
nxtBig[he] = v;
sum_toNext[he] = sum_toN[he] - sum_toN[v];
me.erase(me.begin());
}
if(v < n) me.insert({s[v], v});
return me;
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n = N, s = S, p = P, w = W, l = L;
for(int i=0; i<n; ++i) {
nxtBig[i] = -1;
}
for(int i=0; i<n; ++i) {
g[w[i]].push_back(i);
}
dfs(n);
}
const int anax = 1e7;
long long simulate(int x, int z) {
long long cz = z;
while(x < n && cz < anax) {
if(cz >= s[x]) {
cz += sum_toNext[x];
x = nxtBig[x];
} else {
cz += s[x];
x = l[x];
}
}
cz += sum_toN[x];
return cz;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
9704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9812 KB |
Output is correct |
2 |
Correct |
275 ms |
103272 KB |
Output is correct |
3 |
Correct |
242 ms |
139692 KB |
Output is correct |
4 |
Correct |
260 ms |
145628 KB |
Output is correct |
5 |
Correct |
477 ms |
59308 KB |
Output is correct |
6 |
Correct |
251 ms |
109528 KB |
Output is correct |
7 |
Correct |
274 ms |
136028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
9840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
9840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
9840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9812 KB |
Output is correct |
2 |
Correct |
275 ms |
103272 KB |
Output is correct |
3 |
Correct |
242 ms |
139692 KB |
Output is correct |
4 |
Correct |
260 ms |
145628 KB |
Output is correct |
5 |
Correct |
477 ms |
59308 KB |
Output is correct |
6 |
Correct |
251 ms |
109528 KB |
Output is correct |
7 |
Correct |
274 ms |
136028 KB |
Output is correct |
8 |
Incorrect |
6 ms |
9840 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |