#include "books.h"
#include <algorithm>
using namespace std;
typedef long long llong;
const int max_n = 1000000;
const int max_cycle = 500001;
int n;
int cycle[max_n];
int cycle_l[max_cycle];
int cycle_r[max_cycle];
int group_par[max_cycle];
int cycle_n = 0;
int uf[max_cycle];
llong near[max_cycle];
llong go_left[max_cycle];
llong go_right[max_cycle];
llong go[max_cycle];
int find(int x) {
if (uf[x]) return uf[x] = find(uf[x]);
return x;
}
long long minimum_walk(vector<int> p, int s) {
llong dist1 = 0ll;
n = p.size();
for (int i = 0; i < n; ++i) {
dist1 += abs(p[i] - i);
if (p[i] != i && cycle[i] == 0) {
cycle[i] = ++cycle_n;
cycle_l[cycle[i]] = i;
cycle_r[cycle[i]] = i;
int j = p[i];
while (i != j) {
cycle[j] = cycle[i];
cycle_r[cycle[i]] = max(cycle_r[cycle[i]], j);
j = p[j];
}
}
}
if (dist1 == 0ll) return 0ll;
vector<int> st;
st.push_back(0);
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
if (cycle_l[cycle[i]] == i) st.push_back(cycle[i]);
else {
int c = find(cycle[i]);
while (c < st.back()) {
int x = st.back();
st.pop_back();
uf[x] = c;
cycle_r[c] = max(cycle_r[c], cycle_r[x]);
}
if (cycle_r[c] == i) {
st.pop_back();
group_par[c] = st.back();
}
}
}
}
bool contain = false;
int right_cycle = 0;
llong dist2 = 0ll;
int l = n + 1, r = -1;
for (int i = 1; i <= cycle_n; ++i) {
group_par[i] = find(group_par[i]);
if (find(i) == i) {
l = min(l, cycle_l[i]);
r = max(r, cycle_r[i]);
if (cycle_l[i] < s && s < cycle_r[i]) contain = 1;
if (right_cycle != 0 && cycle_r[i] < cycle_r[right_cycle]) continue;
if (right_cycle != 0) dist2 += cycle_l[i] - cycle_r[right_cycle];
right_cycle = i;
}
}
if (!contain && l <= s && s <= r) return dist1 + dist2 * 2;
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
int c = find(cycle[i]);
near[c] = i;
if (group_par[c] != 0 && cycle_l[c] == i)
go_left[c] = i - near[group_par[c]];
else if (cycle_r[c] == i)
near[group_par[c]] = max(near[group_par[c]], i - go_left[c]);
}
}
for (int i = n; i--;) {
if (p[i] != i) {
int c = find(cycle[i]);
near[c] = i;
if (group_par[c] != 0 && cycle_r[c] == i)
go_right[c] = near[group_par[c]] - i;
else if (cycle_l[c] == i)
near[group_par[c]] = min(near[group_par[c]], i + go_right[c]);
}
}
for (int i = 1; i <= cycle_n; ++i)
go[i] = min(go_left[i], go_right[i]) + go[group_par[i]];
llong dist3 = 1e18;
for (int i = 0; i < n; ++i) {
if (p[i] != i)
dist3 = min(go[find(cycle[i])] + abs(i - s), dist3);
}
return dist1 + (dist2 + dist3) * 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 16 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 17 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 18 |
Correct |
0 ms |
29276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 16 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 17 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 18 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 19 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 20 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 21 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 22 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 23 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 24 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 25 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 26 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 27 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 28 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 29 |
Correct |
0 ms |
29276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 16 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 17 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 18 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 19 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 20 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 21 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 22 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 23 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 24 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 25 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 26 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 27 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 28 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 29 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 30 |
Correct |
239 ms |
37092 KB |
Output is correct |
| 31 |
Correct |
243 ms |
37092 KB |
Output is correct |
| 32 |
Correct |
169 ms |
37092 KB |
Output is correct |
| 33 |
Correct |
186 ms |
37092 KB |
Output is correct |
| 34 |
Correct |
199 ms |
37092 KB |
Output is correct |
| 35 |
Correct |
143 ms |
37092 KB |
Output is correct |
| 36 |
Correct |
159 ms |
37092 KB |
Output is correct |
| 37 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 38 |
Correct |
153 ms |
37092 KB |
Output is correct |
| 39 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 40 |
Correct |
173 ms |
37092 KB |
Output is correct |
| 41 |
Correct |
196 ms |
37092 KB |
Output is correct |
| 42 |
Correct |
183 ms |
37092 KB |
Output is correct |
| 43 |
Correct |
159 ms |
37092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 16 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 17 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 18 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 19 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 20 |
Correct |
0 ms |
29276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 16 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 17 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 18 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 19 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 20 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 21 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 22 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 23 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 24 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 25 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 26 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 27 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 28 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 29 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 30 |
Correct |
239 ms |
37092 KB |
Output is correct |
| 31 |
Correct |
243 ms |
37092 KB |
Output is correct |
| 32 |
Correct |
169 ms |
37092 KB |
Output is correct |
| 33 |
Correct |
186 ms |
37092 KB |
Output is correct |
| 34 |
Correct |
199 ms |
37092 KB |
Output is correct |
| 35 |
Correct |
143 ms |
37092 KB |
Output is correct |
| 36 |
Correct |
159 ms |
37092 KB |
Output is correct |
| 37 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 38 |
Correct |
153 ms |
37092 KB |
Output is correct |
| 39 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 40 |
Correct |
173 ms |
37092 KB |
Output is correct |
| 41 |
Correct |
196 ms |
37092 KB |
Output is correct |
| 42 |
Correct |
183 ms |
37092 KB |
Output is correct |
| 43 |
Correct |
159 ms |
37092 KB |
Output is correct |
| 44 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 45 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 46 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 47 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 48 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 49 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 50 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 51 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 52 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 53 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 54 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 55 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 56 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 57 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 58 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 59 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 60 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 61 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 62 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 63 |
Correct |
0 ms |
29276 KB |
Output is correct |
| 64 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 65 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 66 |
Correct |
183 ms |
37092 KB |
Output is correct |
| 67 |
Correct |
179 ms |
37092 KB |
Output is correct |
| 68 |
Correct |
13 ms |
30060 KB |
Output is correct |
| 69 |
Correct |
13 ms |
30060 KB |
Output is correct |
| 70 |
Correct |
13 ms |
30060 KB |
Output is correct |
| 71 |
Correct |
13 ms |
30060 KB |
Output is correct |
| 72 |
Correct |
13 ms |
30060 KB |
Output is correct |
| 73 |
Correct |
16 ms |
30060 KB |
Output is correct |
| 74 |
Correct |
156 ms |
37092 KB |
Output is correct |
| 75 |
Correct |
136 ms |
37092 KB |
Output is correct |
| 76 |
Correct |
206 ms |
37092 KB |
Output is correct |
| 77 |
Correct |
196 ms |
37092 KB |
Output is correct |
| 78 |
Correct |
173 ms |
37092 KB |
Output is correct |
| 79 |
Correct |
206 ms |
37092 KB |
Output is correct |
| 80 |
Correct |
129 ms |
37092 KB |
Output is correct |
| 81 |
Correct |
166 ms |
40248 KB |
Output is correct |
| 82 |
Correct |
149 ms |
40248 KB |
Output is correct |
| 83 |
Correct |
176 ms |
37364 KB |
Output is correct |
| 84 |
Correct |
179 ms |
37364 KB |
Output is correct |
| 85 |
Correct |
223 ms |
37232 KB |
Output is correct |
| 86 |
Correct |
176 ms |
37092 KB |
Output is correct |
| 87 |
Correct |
179 ms |
38712 KB |
Output is correct |
| 88 |
Correct |
173 ms |
37944 KB |
Output is correct |
| 89 |
Correct |
186 ms |
37560 KB |
Output is correct |
| 90 |
Correct |
199 ms |
37092 KB |
Output is correct |
| 91 |
Correct |
189 ms |
37092 KB |
Output is correct |
| 92 |
Correct |
226 ms |
37092 KB |
Output is correct |
