#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int LOG = 24;
struct Data{
int pos;
ll sum, need;
};
Data combine(Data a, Data b){
Data c;
c.pos = b.pos;
c.sum = a.sum + b.sum;
c.need = min(a.need, b.need-a.sum);
return c;
}
int n;
vector<int> s, p, w, l;
vector<vector<vector<Data>>> jump;
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_;
jump.assign(LOG, vector<vector<Data>>(LOG, vector<Data>(n+1)));
for(int i = 0; i < LOG; i++){
for(int j = 0; j < n; j++){
if(s[j] <= (1<<i)) jump[i][0][j] = {w[j], s[j], INF};
else jump[i][0][j] = {l[j], p[j], s[j]};
}
jump[i][0][n] = {n, 0, 0};
for(int k = 1; k < LOG; k++){
for(int j = 0; j <= n; j++){
jump[i][k][j] = combine(jump[i][k-1][j], jump[i][k-1][jump[i][k-1][j].pos]);
}
}
}
}
ll simulate(int x, int z) {
ll ans = z;
while(x != n){
if(ans >= s[x]){
ans += s[x];
x = w[x];
continue;
}
int layer;
for(layer = 0; layer <= LOG && ans >= (1<<layer); layer++);
layer--;
Data d{x, ans, INF};
for(int k = LOG-1; k >= 0; k--){
Data d2 = combine(d, jump[layer][k][d.pos]);
if(d2.need > 0) d = d2;
}
ans = d.sum;
x = d.pos;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
17 ms |
28668 KB |
Output is correct |
4 |
Correct |
492 ms |
709344 KB |
Output is correct |
5 |
Correct |
17 ms |
28628 KB |
Output is correct |
6 |
Correct |
458 ms |
709240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14548 KB |
Output is correct |
2 |
Runtime error |
1377 ms |
2097152 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14548 KB |
Output is correct |
2 |
Correct |
662 ms |
710812 KB |
Output is correct |
3 |
Correct |
2991 ms |
710700 KB |
Output is correct |
4 |
Correct |
3411 ms |
710284 KB |
Output is correct |
5 |
Correct |
2507 ms |
710076 KB |
Output is correct |
6 |
Correct |
648 ms |
710352 KB |
Output is correct |
7 |
Correct |
550 ms |
710396 KB |
Output is correct |
8 |
Correct |
3574 ms |
710224 KB |
Output is correct |
9 |
Correct |
511 ms |
710100 KB |
Output is correct |
10 |
Correct |
3259 ms |
710024 KB |
Output is correct |
11 |
Correct |
619 ms |
710332 KB |
Output is correct |
12 |
Correct |
659 ms |
710408 KB |
Output is correct |
13 |
Correct |
588 ms |
710348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14548 KB |
Output is correct |
2 |
Correct |
662 ms |
710812 KB |
Output is correct |
3 |
Correct |
2991 ms |
710700 KB |
Output is correct |
4 |
Correct |
3411 ms |
710284 KB |
Output is correct |
5 |
Correct |
2507 ms |
710076 KB |
Output is correct |
6 |
Correct |
648 ms |
710352 KB |
Output is correct |
7 |
Correct |
550 ms |
710396 KB |
Output is correct |
8 |
Correct |
3574 ms |
710224 KB |
Output is correct |
9 |
Correct |
511 ms |
710100 KB |
Output is correct |
10 |
Correct |
3259 ms |
710024 KB |
Output is correct |
11 |
Correct |
619 ms |
710332 KB |
Output is correct |
12 |
Correct |
659 ms |
710408 KB |
Output is correct |
13 |
Correct |
588 ms |
710348 KB |
Output is correct |
14 |
Correct |
9 ms |
14520 KB |
Output is correct |
15 |
Correct |
509 ms |
710580 KB |
Output is correct |
16 |
Correct |
518 ms |
710736 KB |
Output is correct |
17 |
Correct |
1865 ms |
710096 KB |
Output is correct |
18 |
Correct |
1869 ms |
710276 KB |
Output is correct |
19 |
Correct |
632 ms |
710476 KB |
Output is correct |
20 |
Correct |
3144 ms |
710080 KB |
Output is correct |
21 |
Correct |
3092 ms |
710220 KB |
Output is correct |
22 |
Correct |
701 ms |
710220 KB |
Output is correct |
23 |
Correct |
557 ms |
710480 KB |
Output is correct |
24 |
Correct |
695 ms |
710444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14548 KB |
Output is correct |
2 |
Correct |
662 ms |
710812 KB |
Output is correct |
3 |
Correct |
2991 ms |
710700 KB |
Output is correct |
4 |
Correct |
3411 ms |
710284 KB |
Output is correct |
5 |
Correct |
2507 ms |
710076 KB |
Output is correct |
6 |
Correct |
648 ms |
710352 KB |
Output is correct |
7 |
Correct |
550 ms |
710396 KB |
Output is correct |
8 |
Correct |
3574 ms |
710224 KB |
Output is correct |
9 |
Correct |
511 ms |
710100 KB |
Output is correct |
10 |
Correct |
3259 ms |
710024 KB |
Output is correct |
11 |
Correct |
619 ms |
710332 KB |
Output is correct |
12 |
Correct |
659 ms |
710408 KB |
Output is correct |
13 |
Correct |
588 ms |
710348 KB |
Output is correct |
14 |
Correct |
9 ms |
14520 KB |
Output is correct |
15 |
Correct |
509 ms |
710580 KB |
Output is correct |
16 |
Correct |
518 ms |
710736 KB |
Output is correct |
17 |
Correct |
1865 ms |
710096 KB |
Output is correct |
18 |
Correct |
1869 ms |
710276 KB |
Output is correct |
19 |
Correct |
632 ms |
710476 KB |
Output is correct |
20 |
Correct |
3144 ms |
710080 KB |
Output is correct |
21 |
Correct |
3092 ms |
710220 KB |
Output is correct |
22 |
Correct |
701 ms |
710220 KB |
Output is correct |
23 |
Correct |
557 ms |
710480 KB |
Output is correct |
24 |
Correct |
695 ms |
710444 KB |
Output is correct |
25 |
Correct |
474 ms |
709752 KB |
Output is correct |
26 |
Correct |
627 ms |
710744 KB |
Output is correct |
27 |
Correct |
471 ms |
710204 KB |
Output is correct |
28 |
Correct |
490 ms |
710112 KB |
Output is correct |
29 |
Correct |
732 ms |
710592 KB |
Output is correct |
30 |
Correct |
3598 ms |
710412 KB |
Output is correct |
31 |
Correct |
3610 ms |
710288 KB |
Output is correct |
32 |
Correct |
726 ms |
710292 KB |
Output is correct |
33 |
Correct |
2617 ms |
710452 KB |
Output is correct |
34 |
Correct |
2605 ms |
710372 KB |
Output is correct |
35 |
Correct |
1068 ms |
710260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14548 KB |
Output is correct |
2 |
Runtime error |
1377 ms |
2097152 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |