This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1000010;
int fa[maxn], sz[maxn];
void init() {
for(int i = 0; i < maxn; i++) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int u) {
if(fa[u] == u) return u;
else return fa[u] = find(fa[u]);
}
void mrg(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
fa[v] = u;
sz[u] += sz[v];
}
int N, S;
int A[maxn], vis[maxn];
vector<pii> E[maxn];
ll minimum_walk(std::vector<int> p, int s) {
N = p.size();
S = s;
for(int i = 0; i < N; i++) {
A[i] = p[i];
}
init();
ll ret = 0;
for(int i = 0; i < N; i++) {
if(vis[i]) continue;
int mx = i;
int u = i;
while(!vis[u]) {
vis[u] = 1;
mx = max(mx, u);
ret += abs(u - A[u]);
mrg(u, A[u]);
u = A[u];
}
}
int st = -1;
for(int i = 0; i < N; i++) {
if(i == S || sz[ find(i) ] > 1) {
if(st != -1) {
E[i - st].push_back(pii(st, i));
}
st = i;
}
}
for(int i = 1; i <= N; i++) {
for(int j = 0; j < E[i].size(); j++) {
int u = E[i][j].first;
int v = E[i][j].second;
if(find(u) != find(v)) {
ret += 2 * i;
mrg(u, v);
}
}
}
return ret;
}
Compilation message (stderr)
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:70:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < E[i].size(); j++) {
~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |