#include "jumps.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 10, lg = 18;
vector<int> nei[N], ch[N];
int lft[N];
int rgt[N];
int Mn[N];
int seen[N];
int idk[N];
int par[N];
bool sub1 = true;
int st[N], en[N], hei[N],Cur = 1, Par[N][lg], dt[N][lg];
void dfs(int u,int p = 0){
hei[u] = hei[p] + 1;
st[u] = Cur++;
Par[u][0] = p;
if (idk[u])
Par[u][0] = idk[u];
for (int i=1;i<=lg;i++)
Par[u][i] = Par[Par[u][i-1]][i-1];
for (int i : ch[u])
dfs(i,u);
en[u] = Cur++;
}
void init(int n,vector<int> h){
vector<int> v;
for (int i=0;i<n;i++)
sub1 &= (h[i] == i + 1);
for (int i=0;i<n;i++)
lft[i] = rgt[i] = -1;
for (int i=0;i<n;i++){
while (v.size() > 0 and h[v.back()] < h[i])
rgt[v.back()] = i,v.pop_back();
v.push_back(i);
}
v.clear();
for (int i=n-1;i>=0;i--){
while (v.size() > 0 and h[v.back()] < h[i])
lft[v.back()] = i,v.pop_back();
v.push_back(i);
}
for (int i=0;i<n;i++){
if (lft[i] != -1)
nei[i + 1].push_back(lft[i] + 1);
if (rgt[i] != -1)
nei[i + 1].push_back(rgt[i] + 1);
}
int rt;
for (int i=0;i<n;i++){
if (lft[i] == -1 and rgt[i] == -1){
rt = i + 1;
continue;
}
int to = rgt[i] + 1;
if (rgt[i] == -1 or (lft[i] != -1 and h[lft[i]] < h[rgt[i]]))
to = lft[i] + 1;
ch[to].push_back(i + 1);
par[i + 1] = to;
if (rgt[i] == -1 or lft[i] == -1)
continue;
idk[i + 1] = lft[i] + rgt[i] + 2 - to;
}
dfs(rt);
}
int dist(int A,int C){
if ( !(st[C] <= st[A] and en[C] >= en[A]) )
return -1;
int d = 1;
for (int i=lg;i>=0;i--)
if (hei[Par[A][i]] > hei[C])
d += (1<<i), A = Par[A][i];
return d;
}
int cur = 0;
int minimum_jumps(int A, int B, int C, int D) {
if (sub1)
return C - B;
if (A == B and C == D)
return dist(A + 1,C + 1);
cur++;
queue<int> Q;
for (int i=A+1;i<=B + 1;i++)
Q.push(i),seen[i] = cur,Mn[i] = 0;
while (!Q.empty()){
int u = Q.front();
if (u >= C+1 and u <= D+1)
return Mn[u];
Q.pop();
for (int i : nei[u])
if (seen[i] != cur)
Mn[i] = Mn[u] + 1,Q.push(i),seen[i] = cur;
}
return -1;
}
Compilation message
jumps.cpp: In function 'void dfs(int, int)':
jumps.cpp:32:19: warning: iteration 17 invokes undefined behavior [-Waggressive-loop-optimizations]
32 | Par[u][i] = Par[Par[u][i-1]][i-1];
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:31:19: note: within this loop
31 | for (int i=1;i<=lg;i++)
| ~^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:94:8: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
94 | dfs(rt);
| ~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
15960 KB |
Output is correct |
2 |
Correct |
4 ms |
15960 KB |
Output is correct |
3 |
Correct |
115 ms |
48880 KB |
Output is correct |
4 |
Correct |
557 ms |
55196 KB |
Output is correct |
5 |
Correct |
489 ms |
35280 KB |
Output is correct |
6 |
Correct |
620 ms |
55192 KB |
Output is correct |
7 |
Correct |
457 ms |
43940 KB |
Output is correct |
8 |
Correct |
576 ms |
55052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18008 KB |
Output is correct |
2 |
Correct |
3 ms |
16156 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
4 ms |
15960 KB |
Output is correct |
5 |
Incorrect |
5 ms |
18008 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18008 KB |
Output is correct |
2 |
Correct |
3 ms |
16156 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Correct |
4 ms |
15960 KB |
Output is correct |
5 |
Incorrect |
5 ms |
18008 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18008 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
4 ms |
15960 KB |
Output is correct |
4 |
Correct |
3 ms |
15960 KB |
Output is correct |
5 |
Correct |
53 ms |
39048 KB |
Output is correct |
6 |
Correct |
65 ms |
42832 KB |
Output is correct |
7 |
Correct |
34 ms |
31320 KB |
Output is correct |
8 |
Correct |
80 ms |
42792 KB |
Output is correct |
9 |
Correct |
13 ms |
20564 KB |
Output is correct |
10 |
Correct |
69 ms |
42756 KB |
Output is correct |
11 |
Correct |
58 ms |
55188 KB |
Output is correct |
12 |
Correct |
67 ms |
52420 KB |
Output is correct |
13 |
Correct |
57 ms |
52168 KB |
Output is correct |
14 |
Correct |
64 ms |
43032 KB |
Output is correct |
15 |
Correct |
69 ms |
54648 KB |
Output is correct |
16 |
Correct |
67 ms |
56628 KB |
Output is correct |
17 |
Correct |
76 ms |
56720 KB |
Output is correct |
18 |
Correct |
3 ms |
15960 KB |
Output is correct |
19 |
Correct |
4 ms |
18008 KB |
Output is correct |
20 |
Correct |
4 ms |
18176 KB |
Output is correct |
21 |
Correct |
4 ms |
18008 KB |
Output is correct |
22 |
Correct |
4 ms |
18008 KB |
Output is correct |
23 |
Correct |
5 ms |
18176 KB |
Output is correct |
24 |
Correct |
4 ms |
18008 KB |
Output is correct |
25 |
Correct |
4 ms |
18008 KB |
Output is correct |
26 |
Correct |
4 ms |
18264 KB |
Output is correct |
27 |
Correct |
4 ms |
18264 KB |
Output is correct |
28 |
Incorrect |
4 ms |
18264 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15956 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Incorrect |
139 ms |
28504 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
15956 KB |
Output is correct |
2 |
Correct |
3 ms |
15960 KB |
Output is correct |
3 |
Correct |
3 ms |
15960 KB |
Output is correct |
4 |
Incorrect |
139 ms |
28504 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
15960 KB |
Output is correct |
2 |
Correct |
4 ms |
15960 KB |
Output is correct |
3 |
Correct |
115 ms |
48880 KB |
Output is correct |
4 |
Correct |
557 ms |
55196 KB |
Output is correct |
5 |
Correct |
489 ms |
35280 KB |
Output is correct |
6 |
Correct |
620 ms |
55192 KB |
Output is correct |
7 |
Correct |
457 ms |
43940 KB |
Output is correct |
8 |
Correct |
576 ms |
55052 KB |
Output is correct |
9 |
Correct |
3 ms |
18008 KB |
Output is correct |
10 |
Correct |
3 ms |
16156 KB |
Output is correct |
11 |
Correct |
3 ms |
15960 KB |
Output is correct |
12 |
Correct |
4 ms |
15960 KB |
Output is correct |
13 |
Incorrect |
5 ms |
18008 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |