Submission #25524

---

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;

const int N_MAX=100000;

template<class T>
class Fenwick_tree{
	int n;
	T a[N_MAX];

public:
	void build(int n){
		this->n=n;
		rep(i,n) a[i]=0;
	}

	void add(int i,T v){
		for(;i<n;i|=i+1) a[i]+=v;
	}

	T sum(int i,int j){
		if(i==0){
			T s=0;
			for(;j>=0;j=(j&(j+1))-1) s+=a[j];
			return s;
		}
		return sum(0,j)-sum(0,i-1);
	}
};

ll count_inversion(int n,const int *a){
	static Fenwick_tree<ll> F;
	F.build(n);
	ll res=0;
	rep(i,n){
		res+=F.sum(a[i]+1,n-1);
		F.add(a[i],1);
	}
	return res;
}

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

	static vector<int> G[100000];
	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;
	static int seq[100000];
	seq[0]=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;
	}

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

	return min(count_inversion(n,seq),count_inversion(n,seq2));
}

Submission Info

Judge Result