#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
int u, v, w;
bool operator < (const thing &b) const {
return w < b.w;
}
};
const int maxn = 1e6 + 5, INF = 1e9;
int vis[maxn];
int last[maxn];
int fa[maxn];
int rt(int u) {
if (fa[u]==u) return u;
else return fa[u] = rt(fa[u]);
}
int minimum_walk(vector<int32_t> p, int32_t s) {
int n = p.size();
for (int i=0;i<n;i++) vis[i] = false;
int ans = 0, cnt = 0;
for (int i=0;i<n;i++) if (!vis[i]) {
if (p[i]==i && i==s) {
cnt++;
vis[i] = cnt;
}
if (p[i]==i) continue;
cnt++;
int u = i;
while (true) {
// cout << cnt << endl;
vis[u] = cnt;
int v = p[u];
ans += abs(v-u);
if (v==i) break;
u = v;
}
}
last[n] = n;
vector<thing> edge;
for (int i=n-1;i>=0;i--) {
if (p[i]!=i || i==s) {
last[i] = i;
if (last[i+1]!=n && vis[last[i+1]]!=vis[i]) edge.push_back({vis[i], vis[last[i+1]], last[i+1] - i});
// cout << i << " " << last[i+1] << " " << vis[last[i+1]] << " " << vis[i] << endl;
} else last[i] = last[i+1];
}
for (int i=1;i<=cnt;i++) fa[i] = i;
sort(edge.begin(), edge.end());
for (auto [u, v, w]:edge) {
if (rt(u)==rt(v)) continue;
ans += w*2;
fa[rt(u)] = rt(v);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
0 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
0 ms |
4444 KB |
Output is correct |
6 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
0 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
0 ms |
4444 KB |
Output is correct |
6 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
0 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
0 ms |
4444 KB |
Output is correct |
6 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '4074' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
0 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
0 ms |
4444 KB |
Output is correct |
6 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |