| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 378119 | rrrr10000 | Ancient Books (IOI17_books) | C++14 | 0 ms | 0 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>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<PP> vpp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outp(T p){cout<<'('<<p.fi<<','<<p.se<<')'<<endl;}
class UF{
vi par,sz;
public:
UF(ll n):par(n,-1),sz(n,1){}
ll root(ll i){
if(par[i]==-1)return i;
return root(par[i]);
}
bool merge(ll a,ll b){
a=root(a);b=root(b);
if(a==b)return false;
if(sz[a]>sz[b])swap(a,b);
par[a]=b;sz[b]+=sz[a];
return true;
}
};
ll minimum_walk(vector<int> p,int s){
int n=p.size();
vi gr(n,-1);
rep(i,n)if(p[i]==i)gr[i]=-2;
ll ans=0,c=0;
rep(i,n)if(gr[i]==-1){
gr[i]=c;
ll nw=p[i];
ans+=abs(nw-i);
while(nw!=i){
gr[nw]=c;
ans+=abs(nw-p[nw]);
nw=p[nw];
}
c++;
}
vpp edge;
rep(i,n)if(gr[i]!=-2){
edge.pb(abs(s-i),c,gr[i]);
ll j=i+1;
while(j<n&&gr[j]==-2)j++;
if(j<n)edge.pb(j-i,gr[i],gr[j]);
}
// outv(gr);
sort(all(edge));
UF uf(c+1);
for(auto x:edge){
// cout<<get<0>(x)<<' '<<get<1>(x)<<' '<<get<2>(x)<<endl;
if(uf.merge(get<1>(x),get<2>(x)))ans+=get<0>(x)*2;
}
return ans;
}
int main(){
ll n;cin>>n;
vector<int> v(n);rep(i,n)cin>>v[i];
out(minimum_walk(v,0));
}