Submission #131380

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define SIZE 100005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct BIT
{
	int bit[SIZE];
	int n;
	
	void init(int _n)
	{
		memset(bit,0,sizeof(bit));
		n=_n;
	}
	void add(int k,int x)
	{
		while(k<=n)
		{
			bit[k]+=x;
			k+=k&-k;
		}
	}
	int sum(int k)
	{
		int ret=0;
		while(k>0)
		{
			ret+=bit[k];
			k-=k&-k;
		}
		return ret;
	}
};
BIT bit;
vector <int> vec[SIZE];
bool use[SIZE];

ll solve(int v,int n)
{
	bit.init(n+2);
	int bef=-1,now=v;
	ll ret=0;
	int cnt=0;
	bool up=true;
	while(up)
	{
		use[now]=true;
		ret+=(ll) bit.sum(now+1);
		bit.add(now+1,1);
		cnt++;
		up=false;
		for(int i=0;i<vec[now].size();i++)
		{
			if(vec[now][i]!=bef)
			{
				int to=vec[now][i];
				bef=now;
				now=to;
				up=true;
				break;
			}
		}
	}
	ll all=(ll) cnt*(ll) (cnt-1)/2;
	return min(all-ret,ret);
}
long long best_swap(int n, int m,int E[][2])
{
	vector <P> in;
	for(int i=0;i<m;i++)
	{
		int l=E[i][0],r=E[i][1];
		if(l>r) swap(l,r);
		in.push_back(P(l,r));
	}
	sort(in.begin(),in.end());
	for(int i=0;i<m;i++)
	{
		if(i>0&&in[i]==in[i-1]) continue;
		int l=in[i].first,r=in[i].second;
		vec[l].push_back(r);
		vec[r].push_back(l);
	}
	for(int i=0;i<n;i++) if(vec[i].size()>2) return -1;
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		if(!use[i]&&vec[i].size()==1)
		{
			ret+=solve(i,n);
		}
	}
	for(int i=0;i<n;i++) if(!use[i]&&vec[i].size()==2) return -1;
	return ret;
}

Submission Info

Judge Result