#include "books.h"
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
//void SO(vector<int>& in){sort(in.begin(),in.end());}
long long minimum_walk(std::vector<int> p, int s) {
llint i,j,n=p.size(),ans=0;
for(i=0;i<n;i++){ans+=abs(p[i]-i);}
vector<int>rop(n,-1);
int ban=0;
for(i=0;i<n;i++){
int gen=i;
if(rop[gen]!=-1){continue;}
if(p[i]==i){continue;}//元からあってるやつは含めない
do{
rop[gen]=ban;
gen=p[gen];
}while(gen!=i);
ban++;
}
//うまくマージしてかっこ列にする
//union-find
if(rop[s]==-1){
rop[s]=ban;
ban++;
}//sはどうしてもループの中にいたい
vector<int>hi(ban,mod);
vector<int>mg(ban);
cerr<<"de"<<__LINE__<<endl;
int zenhi=mod,zenmg=mod;
for(i=0;i<n;i++){
if(rop[i]==-1){continue;}
if(zenhi==mod){zenhi=i;}
zenmg=i;
if(hi[rop[i]]==mod){hi[rop[i]]=i;}
mg[rop[i]]=i;
}
//各ループの端が把握できた
vector<int>oya(ban,-1);
vector<int>uni(ban);
for(i=0;i<n;i++){uni[i]=i;}
stack<int>stk;stk.push(-1);
for(i=0;i<n;i++){
//cerr<<"de"<<__LINE__<<endl;
if(rop[i]==-1){continue;}
int ter=rop[i];
while(uni[ter]!=ter){ter=uni[ter];}
int gen=rop[i];
while(uni[gen]!=ter){
int mto=gen;
gen=uni[gen];
uni[mto]=ter;
}//経路圧縮
//cerr<<"de"<<__LINE__<<endl;
if(hi[ter]==i){stk.push(ter);}
while(-1){
//マージする
int ue=stk.top();
if(ue==ter){break;}
stk.pop();
uni[ue]=ter;
maxeq(mg[ter],mg[ue]);
}
if(mg[ter]==i){stk.pop();oya[ter]=stk.top();}
}
//経路圧縮を極限まですることでO(1)参照します
//これ以降マージをしないので..
for(i=0;i<ban;i++){
int ter=i;
while(uni[ter]!=ter){ter=uni[ter];}
int gen=i;
while(uni[gen]!=ter){
int mto=gen;
gen=uni[gen];
uni[mto]=ter;
}//経路圧縮
}
int dco=uni[rop[s]];
while(oya[dco]!=-1){
int hikyo=0;
int mgkyo=0;
//cerr<<"de"<<__LINE__;
int nobas=hi[dco];
while(rop[nobas]==-1||uni[rop[nobas]]!=uni[oya[dco]]){
hikyo+=2;
nobas--;
if(rop[nobas]!=-1){mineq(nobas,hi[uni[rop[nobas]]]);}
}
//cerr<<"de"<<__LINE__;
nobas=mg[dco];
while(rop[nobas]==-1||uni[rop[nobas]]!=uni[oya[dco]]){
mgkyo+=2;
nobas++;
if(rop[nobas]!=-1){maxeq(nobas,mg[uni[rop[nobas]]]);}
}
//cerr<<"de"<<__LINE__;
ans+=min(hikyo,mgkyo);
dco=uni[oya[dco]];
}
int nobas=hi[dco];
while(nobas!=zenhi){
ans+=2;
nobas--;
if(rop[nobas]!=-1){mineq(nobas,hi[uni[rop[nobas]]]);}
}
nobas=mg[dco];
while(nobas!=zenmg){
ans+=2;
nobas++;
if(rop[nobas]!=-1){maxeq(nobas,mg[uni[rop[nobas]]]);}
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:54:10: warning: unused variable 'j' [-Wunused-variable]
llint i,j,n=p.size(),ans=0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
