Submission #25609

---

Source Code Expand

#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);
	}
};

vector<int> G[100000];

vector<int> b;
ll count_inversion(vector<int> a){
	int n=a.size();
	vector<int> X=a;
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	rep(i,n) a[i]=lower_bound(X.begin(),X.end(),a[i])-X.begin();

	static Fenwick_tree<ll> F;
	F.build(n);
	ll res=0;
	rep(i,a.size()){
		res+=F.sum(a[i]+1,n-1);
		F.add(a[i],1);
	}
	return res;
}
bool vis[100000];

bool dfs1(int u,int pre){
	vis[u]=true;
	rep(i,G[u].size()){
		int v=G[u][i];
		if(v!=pre) if(vis[v] || !dfs1(v,u)) return false;
	}
	return true;
}

vector<int> seq;

ll dfs2(int u,int pre){
	vis[u]=true;
	seq.push_back(u);

	if(G[u].size()==0) return 0;
	if(G[u].size()==1 && pre!=-1){
		ll res=count_inversion(seq);
		reverse(seq.begin(),seq.end());
		res=min(res,count_inversion(seq));
		return res;
	}

	if(G[u][0]!=pre) return dfs2(G[u][0],u);
	else             return dfs2(G[u][1],u);
}

struct edge{
	int u,v;
	bool operator<(const edge &e)const{ return u<e.u || u==e.u && v<e.v; }
	bool operator==(const edge &e)const{ return u==e.u && v==e.v; }
};

ll best_swap(int n,int m,int E_[][2]){
	static edge E[200000];
	rep(i,m){
		E[i].u=min(E_[i][0],E_[i][1]);
		E[i].v=max(E_[i][0],E_[i][1]);
	}
	sort(E,E+m);
	m=unique(E,E+m)-E;

	rep(i,m){
		G[E[i].u].push_back(E[i].v);
		G[E[i].v].push_back(E[i].u);
	}

	rep(u,n) if(G[u].size()>=3) return -1;
	rep(u,n) if(!vis[u] && !dfs1(u,-1)) return -1;

	rep(u,n) vis[u]=false;
	ll res=0;
	rep(u,n) if(!vis[u] && G[u].size()==1) {
		seq.clear();
		res+=dfs2(u,-1);
	}
	return res;
}

Submission Info

Judge Result