Codeforces #789 : Div1 C. Tokitsukaze and Two Colorful Tapes

C問題まで来た割にコード短いな
https://codeforces.com/contest/1677/problem/C

問題

1～NのPermutationである2つの整数列A,Bが与えられる。各値は1～Nとする。
1～NのPermutation Pを任意で定め、A,B中の各値vを、P[v]で置き換えることを考える。
置き換えた後、sum(abs(A[i]-B[i]))の最小値を求めよ。

解法

N頂点の無向グラフを考える。A[i]とB[i]に相当する点を辺でつなぐと、いくつかの閉路ができる。
閉路内の頂点番号が、連番となるようにPを設定すればよい。

int T,N;
int A[101010],B[101010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<101010> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		uf.reinit(N);
		FOR(i,N) uf(A[i]-1,B[i]-1);
		
		int cnt=N;
		FOR(i,N) if(uf[i]==i) cnt-=uf.count(i)%2;
		
		ll ret=0;
		FOR(i,cnt/2) {
			ret+=N-i;
			ret-=1+i;
		}
		cout<<ret*2<<endl;
		
		
		
	}
}

まとめ

本番も結構すんなり解いたな。