Submission #1228697

---

Source Code Expand

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e9
using namespace std;

const int maxn = 101000;

int n,m;

struct edge
{
	int y,nex;
	edge(){}
	edge(const int _y,const int _nex){y=_y;nex=_nex;}
}a[maxn<<1]; int len, fir[maxn];
bool e[maxn<<1];
inline void ins(const int x,const int y){a[++len]=edge(y,fir[x]);fir[x]=len;}

int cir[maxn],cn;
bool inc[maxn];
int t[maxn],tp;
bool v[maxn];
bool f_cir(const int x,const int pre)
{
	if(v[x])
	{
		int la=0;
		while(la!=x) inc[cir[++cn]=la=t[tp--]]=true;
		return true;
	}
	v[x]=true; t[++tp]=x;
	if(x==6||x==15)
	{
		int ii=1;
	}
	for(int k=fir[x];k;k=a[k].nex) if(k!=(pre^1))
	{
		if(f_cir(a[k].y,k)) return true;
	}
	tp--;
	return false;
}

int col[maxn],num[2];
void Color(const int x,const int ff)
{
	num[col[x]==1]++;
	for(int k=fir[x];k;k=a[k].nex)
	{
		const int y=a[k].y;
		if(inc[y]||y==ff) continue;
		
		col[y]=-col[x];
		Color(y,x);
	}
}
int s[maxn],o[maxn];
int dfs(const int x,const int ff)
{
	s[x]=0;
	int re=col[x];
	for(int k=fir[x];k;k=a[k].nex)if(!e[k])
	{
		const int y=a[k].y;
		if(inc[y]||y==ff) continue;
		int tmp=dfs(y,x);
		s[x]+=s[y]+abs(tmp);
		re+=tmp;
	}
	return re;
}

int solve()
{
	t[tp=1]=0;
	int la=0;
	for(int i=2;i<=cn;i++)
	{
		la+=o[cir[i]];
		t[++tp]=-la;
	}
	int mid=(1+tp)>>1;
	std::nth_element(t+1,t+mid,t+tp+1);
	int ans=0,A=t[mid];
	for(int i=1;i<=tp;i++) ans+=abs(A-t[i]);
	return ans;
}

int main()
{
	int T; T=1; int ti=0;
	while(T--)
	{
		ti++;
		len=1; memset(fir,0,sizeof fir);
		
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) inc[i]=false;
		for(int i=1;i<=m;i++)
		{
			int x,y; scanf("%d%d",&x,&y);
			ins(x,y); ins(y,x);
		}
		
		num[0]=num[1]=0;
		if(n==m+1)
		{
			col[1]=-1; Color(1,0);
			if(num[0]!=num[1]) { printf("-1\n"); continue; }
			int k=dfs(1,0);
			printf("%d\n",s[1]);
		}
		else
		{
			cn=0; tp=0; for(int i=1;i<=n;i++) v[i]=false;
			bool flag=f_cir(1,0);
			
			for(int i=1;i<=cn;i++) col[cir[i]]=(i&1)?1:-1,Color(cir[i],0);
			if(cn&1)
			{
				if((num[0]&1)!=(num[1]&1)) { printf("-1\n"); continue; }
				if(num[0]<num[1])
				{
					swap(num[0],num[1]);
					for(int i=1;i<=n;i++) col[i]=-col[i];
				}
				int ek,re=0;
				for(int k=fir[cir[1]];k;k=a[k].nex) if(a[k].y==cir[cn])
				{
					e[ek=k]=true; e[ek^1]=true;
					int tmp=(num[0]-num[1])>>1;
					col[cir[1]]+=tmp;
					col[cir[cn]]+=tmp;
					re+=tmp;
					break;
				}
				for(int i=1;i<=cn;i++) inc[cir[i]]=false;
				int k=dfs(1,0);
				e[ek]=false; e[ek^1]=false;
				printf("%d\n",re+s[1]);
			}
			else
			{
				if(num[0]!=num[1]) { printf("-1\n"); continue; }
				int re=0;
				for(int i=1;i<=cn;i++) o[cir[i]]=dfs(cir[i],0),re+=s[cir[i]];
				
				printf("%d\n",re+solve());
			}
		}
	}
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
                      ^
./Main.cpp:117:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    int x,y; scanf("%d%d",&x,&y);
                                ^

Judge Result