Submission #25244

---

Source Code Expand

#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

ll best_swap(int n,int m,int E[][2]){
	rep(i,m) if(E[i][0]==E[i][1]) for(;;);

	if(n==1) return 0;
	if(n>1000) return -1;

	vector<int> G[1000];
	rep(i,m){
		G[E[i][0]].push_back(E[i][1]);
		G[E[i][1]].push_back(E[i][0]);
	}

	int u0=-1;
	rep(u,n) if(G[u].size()==1) u0=u;
	if(u0==-1) return -1;

	int u=u0,pre=-1;
	int seq[1000]={u0};
	rep(i,n-1){
		int tmp=u;
		if(G[u][0]!=pre) u=G[u][0];
		else             u=G[u][1];
		seq[i+1]=u;
		pre=tmp;
	}

	int seq2[1000];
	rep(i,n) seq2[i]=seq[n-i-1];

	int ans1=0;
	rep(i,n) rep(j,n-i-1) if(seq[j]>seq[j+1]) swap(seq[j],seq[j+1]), ans1++; // ばぶる～

	int ans2=0;
	rep(i,n) rep(j,n-i-1) if(seq2[j]>seq2[j+1]) swap(seq2[j],seq2[j+1]), ans2++;

	return min(ans1,ans2);
}

Submission Info

Judge Result