# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
73491 | mr_banana | Ancient Books (IOI17_books) | C++17 | 4 ms | 636 KiB |
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 <bits/stdc++.h>
#include "books.h"
using namespace std;
const int MN=1e5+100;
int mark[MN];
vector<pair<int,pair<int,int> > > e;
int par[MN];
int root(int x){
return par[x]==x?x:par[x]=root(par[x]);
}
bool merg(int u,int v){
u=root(u),v=root(v);
if(u==v){
return 0;
}
par[v]=u;
return 1;
}
long long minimum_walk(std::vector<int> p, int s) {
int n=p.size();
long long ans=0;
int cnt=0;
for(int i=0;i<n;i++){
ans+=abs(p[i]-i);
if(!mark[i] && p[i]!=i){
int x=i;
do{
mark[x]=cnt;
x=p[x];
}while(x!=i);
cnt++;
}
}
for(int i=0;i<n;i++){
if(p[i]!=i){
for(int j=i+1;j<n;j++){
if(p[j]!=j){
e.push_back({j-i,{mark[i],mark[j]}});
break;
}
}
}
}
sort(e.begin(),e.end());
for(int i=0;i<e.size();i++){
if(merg(e[i].second.first,e[i].second.second)){
ans+=2*e[i].first;
}
}
if(ans){
for(int i=0;i<n;i++){
if(p[i]==i){
ans+=2;
}
else{
break;
}
}
}
return ans;
}
Compilation message (stderr)
# | 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... |