#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
const int MAXC = 10000000;
struct node {
int to, lower;
ll sum;
node operator+(const node &a) const {
node rt;
rt.to = a.to;
rt.sum = sum + a.sum;
if (lower + sum < a.lower)
rt.lower = a.lower - sum;
else
rt.lower = lower;
return rt;
}
};
struct node2 {
int to;
ll upper, sum;
node2 operator+(const node2 &a) const {
node2 rt;
rt.to = a.to;
rt.sum = sum + a.sum;
if (a.upper == MAXC + 1)
rt.upper = upper;
else if (upper + sum > a.upper)
rt.upper = a.upper - sum;
else
rt.upper = upper;
return rt;
}
};
int N, lg = __lg(MAXC);
vector<int> S, P, W, L;
vector<node> dp[30];
vector<node2> dp2[30];
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;
dp[0].resize(N + 1);
dp[0][N] = node{N, 0, 0};
for (int i = 0; i < N; ++i)
dp[0][i] = node{W[i], S[i], (ll)S[i]};
for (int i = 1; i <= lg; ++i) {
dp[i].resize(N + 1);
for (int j = 0; j <= N; ++j)
dp[i][j] = dp[i - 1][j] + dp[i - 1][dp[i - 1][j].to];
}
dp2[0].resize(N + 1);
dp2[0][N] = node2{N, 0LL, 0LL};
for (int i = 0; i < N; ++i)
dp2[0][i] = node2{L[i], S[i] - 1, (ll)P[i]};
for (int i = 1; i <= lg; ++i) {
dp2[i].resize(N + 1);
for (int j = 0; j <= N; ++j)
dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][dp2[i - 1][j].to];
}
}
long long simulate(int x, int z) {
ll nw = z;
while (dp[lg][x].lower > nw) {
for (int i = lg; i >= 0; --i)
if (dp[i][x].lower <= nw) {
nw += dp[i][x].sum;
x = dp[i][x].to;
}
for (int i = lg; i >= 0; --i)
if (dp2[i][x].upper >= nw) {
nw += dp2[i][x].sum;
x = dp2[i][x].to;
}
}
return nw + dp[lg][x].sum;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
3 ms |
2252 KB |
Output is correct |
4 |
Correct |
57 ms |
49592 KB |
Output is correct |
5 |
Correct |
3 ms |
2252 KB |
Output is correct |
6 |
Correct |
56 ms |
49584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
565 ms |
395732 KB |
Output is correct |
3 |
Correct |
484 ms |
395748 KB |
Output is correct |
4 |
Correct |
484 ms |
395588 KB |
Output is correct |
5 |
Correct |
580 ms |
395576 KB |
Output is correct |
6 |
Correct |
570 ms |
395600 KB |
Output is correct |
7 |
Correct |
508 ms |
395560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
101 ms |
50512 KB |
Output is correct |
3 |
Correct |
109 ms |
50412 KB |
Output is correct |
4 |
Correct |
74 ms |
50372 KB |
Output is correct |
5 |
Correct |
74 ms |
50376 KB |
Output is correct |
6 |
Correct |
130 ms |
50368 KB |
Output is correct |
7 |
Correct |
128 ms |
51040 KB |
Output is correct |
8 |
Correct |
83 ms |
50944 KB |
Output is correct |
9 |
Correct |
88 ms |
50944 KB |
Output is correct |
10 |
Correct |
74 ms |
50904 KB |
Output is correct |
11 |
Correct |
142 ms |
51012 KB |
Output is correct |
12 |
Correct |
195 ms |
51040 KB |
Output is correct |
13 |
Correct |
185 ms |
51012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
101 ms |
50512 KB |
Output is correct |
3 |
Correct |
109 ms |
50412 KB |
Output is correct |
4 |
Correct |
74 ms |
50372 KB |
Output is correct |
5 |
Correct |
74 ms |
50376 KB |
Output is correct |
6 |
Correct |
130 ms |
50368 KB |
Output is correct |
7 |
Correct |
128 ms |
51040 KB |
Output is correct |
8 |
Correct |
83 ms |
50944 KB |
Output is correct |
9 |
Correct |
88 ms |
50944 KB |
Output is correct |
10 |
Correct |
74 ms |
50904 KB |
Output is correct |
11 |
Correct |
142 ms |
51012 KB |
Output is correct |
12 |
Correct |
195 ms |
51040 KB |
Output is correct |
13 |
Correct |
185 ms |
51012 KB |
Output is correct |
14 |
Correct |
2 ms |
1228 KB |
Output is correct |
15 |
Correct |
332 ms |
50836 KB |
Output is correct |
16 |
Correct |
106 ms |
51100 KB |
Output is correct |
17 |
Correct |
86 ms |
51052 KB |
Output is correct |
18 |
Correct |
80 ms |
50704 KB |
Output is correct |
19 |
Correct |
168 ms |
50756 KB |
Output is correct |
20 |
Correct |
136 ms |
50672 KB |
Output is correct |
21 |
Correct |
106 ms |
50756 KB |
Output is correct |
22 |
Execution timed out |
7041 ms |
50664 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
101 ms |
50512 KB |
Output is correct |
3 |
Correct |
109 ms |
50412 KB |
Output is correct |
4 |
Correct |
74 ms |
50372 KB |
Output is correct |
5 |
Correct |
74 ms |
50376 KB |
Output is correct |
6 |
Correct |
130 ms |
50368 KB |
Output is correct |
7 |
Correct |
128 ms |
51040 KB |
Output is correct |
8 |
Correct |
83 ms |
50944 KB |
Output is correct |
9 |
Correct |
88 ms |
50944 KB |
Output is correct |
10 |
Correct |
74 ms |
50904 KB |
Output is correct |
11 |
Correct |
142 ms |
51012 KB |
Output is correct |
12 |
Correct |
195 ms |
51040 KB |
Output is correct |
13 |
Correct |
185 ms |
51012 KB |
Output is correct |
14 |
Correct |
2 ms |
1228 KB |
Output is correct |
15 |
Correct |
332 ms |
50836 KB |
Output is correct |
16 |
Correct |
106 ms |
51100 KB |
Output is correct |
17 |
Correct |
86 ms |
51052 KB |
Output is correct |
18 |
Correct |
80 ms |
50704 KB |
Output is correct |
19 |
Correct |
168 ms |
50756 KB |
Output is correct |
20 |
Correct |
136 ms |
50672 KB |
Output is correct |
21 |
Correct |
106 ms |
50756 KB |
Output is correct |
22 |
Execution timed out |
7041 ms |
50664 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
565 ms |
395732 KB |
Output is correct |
3 |
Correct |
484 ms |
395748 KB |
Output is correct |
4 |
Correct |
484 ms |
395588 KB |
Output is correct |
5 |
Correct |
580 ms |
395576 KB |
Output is correct |
6 |
Correct |
570 ms |
395600 KB |
Output is correct |
7 |
Correct |
508 ms |
395560 KB |
Output is correct |
8 |
Correct |
2 ms |
1228 KB |
Output is correct |
9 |
Correct |
101 ms |
50512 KB |
Output is correct |
10 |
Correct |
109 ms |
50412 KB |
Output is correct |
11 |
Correct |
74 ms |
50372 KB |
Output is correct |
12 |
Correct |
74 ms |
50376 KB |
Output is correct |
13 |
Correct |
130 ms |
50368 KB |
Output is correct |
14 |
Correct |
128 ms |
51040 KB |
Output is correct |
15 |
Correct |
83 ms |
50944 KB |
Output is correct |
16 |
Correct |
88 ms |
50944 KB |
Output is correct |
17 |
Correct |
74 ms |
50904 KB |
Output is correct |
18 |
Correct |
142 ms |
51012 KB |
Output is correct |
19 |
Correct |
195 ms |
51040 KB |
Output is correct |
20 |
Correct |
185 ms |
51012 KB |
Output is correct |
21 |
Correct |
2 ms |
1228 KB |
Output is correct |
22 |
Correct |
332 ms |
50836 KB |
Output is correct |
23 |
Correct |
106 ms |
51100 KB |
Output is correct |
24 |
Correct |
86 ms |
51052 KB |
Output is correct |
25 |
Correct |
80 ms |
50704 KB |
Output is correct |
26 |
Correct |
168 ms |
50756 KB |
Output is correct |
27 |
Correct |
136 ms |
50672 KB |
Output is correct |
28 |
Correct |
106 ms |
50756 KB |
Output is correct |
29 |
Execution timed out |
7041 ms |
50664 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |