#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using ll = long long;
int n;
vector<int> s, p, w, l;
const int INF = 1e7;
const int N = 50001;
namespace sub2 {
const int N = 400010;
vector<int> g[N];
int anc[N][19];
ll bl[N][19], sum[N];
void dfs(int cur, int p) {
anc[cur][0] = p;
for(int i = 1; i < 19; i++)
anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
if(cur != n) {
bl[cur][0] = s[cur] + sum[cur];
for(int i = 1; i < 19; i++)
bl[cur][i] = max(bl[cur][i - 1], bl[anc[cur][i - 1]][i - 1]);
}
for(int to : g[cur]) {
sum[to] = sum[cur] + s[to];
dfs(to, cur);
}
}
int find(int x, ll val) {
val += sum[x];
for(int i = 18; i >= 0; i--) {
if(val >= bl[x][i])
x = anc[x][i];
}
return x;
}
void build() {
for(int i = 0; i < n; i++) {
g[w[i]].push_back(i);
}
dfs(n, n);
}
};
ll d[N];
int sm[24][24][N], to[24][24][N], mn[24][24][N];
void build() {
for(int i = 0; i < 24; i++) {
for(int v = 0; v <= n; v++)
sm[i][0][v] = (s[v] < (1 << i) ? s[v] : p[v]),
to[i][0][v] = (s[v] < (1 << i) ? w[v] : l[v]),
mn[i][0][v] = (s[v] < (1 << i) ? INF : s[v]);
for(int j = 1; j < 24; j++) {
for(int v = 0; v <= n; v++) {
sm[i][j][v] = min(sm[i][j - 1][v] + sm[i][j - 1][ to[i][j - 1][v] ], INF);
to[i][j][v] = to[i][j - 1][ to[i][j - 1][v] ];
mn[i][j][v] = min(mn[i][j - 1][v], mn[i][j - 1][ to[i][j - 1][v] ] - sm[i][j - 1][v]);
}
}
}
}
bool Key = 1;
void init(int N, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1) {
n = N; s = s1; p = p1; w = w1; l = l1;
s.push_back(0); p.push_back(0);
w.push_back(n); l.push_back(n);
for(int i = 0; i < n; i++) Key &= (s[i] == p[i]);
if(Key) {
sub2::build();
return;
}
d[n] = 0;
for(int i = n - 1; i >= 0; i--)
d[i] = s[i] + d[w[i]];
build();
}
int level(long long x) {
return 63 - __builtin_clzll(x);
}
ll find(int v, ll initial) {
while(v != n && initial <= INF) {
int lev = level(initial);
for(int k = 23; k >= 0; k--) {
if(initial < mn[lev][k][v] && initial + sm[lev][k][v] <= INF) {
initial += sm[lev][k][v];
v = to[lev][k][v];
}
}
bool flag = (initial < s[v]);
initial += (flag ? p[v] : s[v]);
v = (flag ? l[v] : w[v]);
}
initial += d[v];
return initial;
}
long long simulate(int x, int z) {
if(Key) {
ll res = z;
while(x != n) {
int next = sub2::find(x, res);
res += sub2::sum[x] - sub2::sum[next];
x = next;
if(x == n) break;
res += p[x];
x = l[x];
}
return res;
}
return find(x, z);
}
/*
Draft
Idea for 100 pnts
Observation: if will compare the value when will defeat the monster we not used to defeat with initial value we'll see that value raised by 2
So we can divide interval [1, 1e7] by powers of 2
=> so it'll look like: (1, 1), (2, 3), (4, 7), (8, 15), (16, 31), (32, 63) ... (2 ^ k, 2 ^ (k + 1) - 1)
(P.S. There's log(A) = 24 segments totally.)
(*) Assume that we can jump over the monsters whose strength's segment is smaller than our's segment
=> for every such monster - i there is such k that following condition is fullfilled s[i] <= 2 ^ k <= cur_val
So after the jump we'll meet the monster whose strength was less than ours, but now we can defeat him
so after our win our val's segment'pointer have moved by one in worst case
So totally we'll do less or equal log(A) such 'jumps'
For jump we should precompute something for every node
sum[v][i][j] = the total value if I had started in v, and defeated only monsters whose stregth is < 2^i, and I did 2^j such moves
initial + W(v, x) >= s[x] and log2(s[x]) >= log2(initial)
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
17236 KB |
Output is correct |
2 |
Correct |
9 ms |
17256 KB |
Output is correct |
3 |
Correct |
19 ms |
30840 KB |
Output is correct |
4 |
Correct |
220 ms |
351576 KB |
Output is correct |
5 |
Correct |
16 ms |
30808 KB |
Output is correct |
6 |
Correct |
190 ms |
351472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9968 KB |
Output is correct |
2 |
Correct |
357 ms |
154652 KB |
Output is correct |
3 |
Correct |
290 ms |
166048 KB |
Output is correct |
4 |
Correct |
281 ms |
167640 KB |
Output is correct |
5 |
Correct |
434 ms |
136736 KB |
Output is correct |
6 |
Correct |
377 ms |
154656 KB |
Output is correct |
7 |
Correct |
298 ms |
164268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24148 KB |
Output is correct |
2 |
Correct |
261 ms |
353032 KB |
Output is correct |
3 |
Correct |
218 ms |
353112 KB |
Output is correct |
4 |
Correct |
218 ms |
352472 KB |
Output is correct |
5 |
Correct |
202 ms |
352444 KB |
Output is correct |
6 |
Correct |
281 ms |
352624 KB |
Output is correct |
7 |
Correct |
278 ms |
352560 KB |
Output is correct |
8 |
Correct |
219 ms |
352380 KB |
Output is correct |
9 |
Correct |
230 ms |
352316 KB |
Output is correct |
10 |
Correct |
216 ms |
352240 KB |
Output is correct |
11 |
Correct |
225 ms |
352628 KB |
Output is correct |
12 |
Correct |
388 ms |
352700 KB |
Output is correct |
13 |
Correct |
273 ms |
352588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24148 KB |
Output is correct |
2 |
Correct |
261 ms |
353032 KB |
Output is correct |
3 |
Correct |
218 ms |
353112 KB |
Output is correct |
4 |
Correct |
218 ms |
352472 KB |
Output is correct |
5 |
Correct |
202 ms |
352444 KB |
Output is correct |
6 |
Correct |
281 ms |
352624 KB |
Output is correct |
7 |
Correct |
278 ms |
352560 KB |
Output is correct |
8 |
Correct |
219 ms |
352380 KB |
Output is correct |
9 |
Correct |
230 ms |
352316 KB |
Output is correct |
10 |
Correct |
216 ms |
352240 KB |
Output is correct |
11 |
Correct |
225 ms |
352628 KB |
Output is correct |
12 |
Correct |
388 ms |
352700 KB |
Output is correct |
13 |
Correct |
273 ms |
352588 KB |
Output is correct |
14 |
Correct |
13 ms |
24148 KB |
Output is correct |
15 |
Correct |
227 ms |
352844 KB |
Output is correct |
16 |
Correct |
236 ms |
353048 KB |
Output is correct |
17 |
Correct |
279 ms |
352444 KB |
Output is correct |
18 |
Correct |
263 ms |
352516 KB |
Output is correct |
19 |
Correct |
279 ms |
352636 KB |
Output is correct |
20 |
Correct |
255 ms |
352432 KB |
Output is correct |
21 |
Correct |
308 ms |
352472 KB |
Output is correct |
22 |
Correct |
206 ms |
352424 KB |
Output is correct |
23 |
Correct |
276 ms |
352656 KB |
Output is correct |
24 |
Correct |
353 ms |
352684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24148 KB |
Output is correct |
2 |
Correct |
261 ms |
353032 KB |
Output is correct |
3 |
Correct |
218 ms |
353112 KB |
Output is correct |
4 |
Correct |
218 ms |
352472 KB |
Output is correct |
5 |
Correct |
202 ms |
352444 KB |
Output is correct |
6 |
Correct |
281 ms |
352624 KB |
Output is correct |
7 |
Correct |
278 ms |
352560 KB |
Output is correct |
8 |
Correct |
219 ms |
352380 KB |
Output is correct |
9 |
Correct |
230 ms |
352316 KB |
Output is correct |
10 |
Correct |
216 ms |
352240 KB |
Output is correct |
11 |
Correct |
225 ms |
352628 KB |
Output is correct |
12 |
Correct |
388 ms |
352700 KB |
Output is correct |
13 |
Correct |
273 ms |
352588 KB |
Output is correct |
14 |
Correct |
13 ms |
24148 KB |
Output is correct |
15 |
Correct |
227 ms |
352844 KB |
Output is correct |
16 |
Correct |
236 ms |
353048 KB |
Output is correct |
17 |
Correct |
279 ms |
352444 KB |
Output is correct |
18 |
Correct |
263 ms |
352516 KB |
Output is correct |
19 |
Correct |
279 ms |
352636 KB |
Output is correct |
20 |
Correct |
255 ms |
352432 KB |
Output is correct |
21 |
Correct |
308 ms |
352472 KB |
Output is correct |
22 |
Correct |
206 ms |
352424 KB |
Output is correct |
23 |
Correct |
276 ms |
352656 KB |
Output is correct |
24 |
Correct |
353 ms |
352684 KB |
Output is correct |
25 |
Correct |
202 ms |
351932 KB |
Output is correct |
26 |
Correct |
255 ms |
353044 KB |
Output is correct |
27 |
Correct |
230 ms |
352460 KB |
Output is correct |
28 |
Correct |
236 ms |
352480 KB |
Output is correct |
29 |
Correct |
245 ms |
352872 KB |
Output is correct |
30 |
Correct |
264 ms |
352844 KB |
Output is correct |
31 |
Correct |
255 ms |
352312 KB |
Output is correct |
32 |
Correct |
357 ms |
352492 KB |
Output is correct |
33 |
Correct |
470 ms |
352572 KB |
Output is correct |
34 |
Correct |
1441 ms |
352452 KB |
Output is correct |
35 |
Correct |
374 ms |
352508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9968 KB |
Output is correct |
2 |
Correct |
357 ms |
154652 KB |
Output is correct |
3 |
Correct |
290 ms |
166048 KB |
Output is correct |
4 |
Correct |
281 ms |
167640 KB |
Output is correct |
5 |
Correct |
434 ms |
136736 KB |
Output is correct |
6 |
Correct |
377 ms |
154656 KB |
Output is correct |
7 |
Correct |
298 ms |
164268 KB |
Output is correct |
8 |
Correct |
14 ms |
24148 KB |
Output is correct |
9 |
Correct |
261 ms |
353032 KB |
Output is correct |
10 |
Correct |
218 ms |
353112 KB |
Output is correct |
11 |
Correct |
218 ms |
352472 KB |
Output is correct |
12 |
Correct |
202 ms |
352444 KB |
Output is correct |
13 |
Correct |
281 ms |
352624 KB |
Output is correct |
14 |
Correct |
278 ms |
352560 KB |
Output is correct |
15 |
Correct |
219 ms |
352380 KB |
Output is correct |
16 |
Correct |
230 ms |
352316 KB |
Output is correct |
17 |
Correct |
216 ms |
352240 KB |
Output is correct |
18 |
Correct |
225 ms |
352628 KB |
Output is correct |
19 |
Correct |
388 ms |
352700 KB |
Output is correct |
20 |
Correct |
273 ms |
352588 KB |
Output is correct |
21 |
Correct |
13 ms |
24148 KB |
Output is correct |
22 |
Correct |
227 ms |
352844 KB |
Output is correct |
23 |
Correct |
236 ms |
353048 KB |
Output is correct |
24 |
Correct |
279 ms |
352444 KB |
Output is correct |
25 |
Correct |
263 ms |
352516 KB |
Output is correct |
26 |
Correct |
279 ms |
352636 KB |
Output is correct |
27 |
Correct |
255 ms |
352432 KB |
Output is correct |
28 |
Correct |
308 ms |
352472 KB |
Output is correct |
29 |
Correct |
206 ms |
352424 KB |
Output is correct |
30 |
Correct |
276 ms |
352656 KB |
Output is correct |
31 |
Correct |
353 ms |
352684 KB |
Output is correct |
32 |
Correct |
202 ms |
351932 KB |
Output is correct |
33 |
Correct |
255 ms |
353044 KB |
Output is correct |
34 |
Correct |
230 ms |
352460 KB |
Output is correct |
35 |
Correct |
236 ms |
352480 KB |
Output is correct |
36 |
Correct |
245 ms |
352872 KB |
Output is correct |
37 |
Correct |
264 ms |
352844 KB |
Output is correct |
38 |
Correct |
255 ms |
352312 KB |
Output is correct |
39 |
Correct |
357 ms |
352492 KB |
Output is correct |
40 |
Correct |
470 ms |
352572 KB |
Output is correct |
41 |
Correct |
1441 ms |
352452 KB |
Output is correct |
42 |
Correct |
374 ms |
352508 KB |
Output is correct |
43 |
Correct |
7 ms |
17260 KB |
Output is correct |
44 |
Correct |
12 ms |
24148 KB |
Output is correct |
45 |
Incorrect |
798 ms |
382204 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |