Submission #1025907

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 100005
#define M 200005
#define seed 23333

using namespace std;
int i,j,m,n,p,k,now[N],size[2][N],fa[N],x,y,Q[N],gtm[N];
vector<int>v[N];
long long ans;
void dfs(int x)
{
		size[now[x]][x]++;
		int i;
		for (i=0;i<(int)v[x].size();++i)
		{
				int p=v[x][i];
				if (fa[x]==p) continue;
				fa[p]=x;
				now[p]=now[x]^1;
				dfs(p);
				size[0][x]+=size[0][p];
				size[1][x]+=size[1][p];
		}
		if (x!=1) ans+=abs(size[0][x]-size[1][x]);
}
void worka()
{
		dfs(1);
		if (size[0][1]==size[1][1]) 	
		cout<<ans<<endl;
		else puts("-1");
}
int sum[N],vis[N];
int find_cycle_length()
{
		for (i=1;i<=n;++i) sum[i]=(int)v[i].size();
		for (i=1;i<=n;++i) if (sum[i]==1) Q[++Q[0]]=i,vis[i]=1;
		int l=1;
		for (l=1;l<=Q[0];++l)
		{
				int p=Q[l];
				for (i=0;i<(int)v[p].size();++i)
				{
						int k=v[p][i];
						--sum[k];
						if (sum[k]==1) vis[k]=1,Q[++Q[0]]=k;
				}
		}
		return n-Q[0];
}
int x_next[N],ga,gb;
void dfs_even(int x)
{
		int i;
		size[now[x]][x]++;
		for (i=0;i<(int)v[x].size();++i)
		{
				int p=v[x][i];
				if ((x==ga&&p==gb)||(x==gb&&p==ga)) continue;
				if (fa[x]==p) continue;
				fa[p]=x;
				now[p]=now[x]^1;
				dfs_even(p);
				size[0][x]+=size[0][p];
				size[1][x]+=size[1][p];
				gtm[x]|=gtm[p];
		}
		if (x!=ga)
		{
			if (!gtm[x]) ans+=abs(size[0][x]-size[1][x]);
			else x_next[++x_next[0]]=size[1][x]-size[0][x];
		}
}
void work_even_cycle()
{
		for (i=1;i<=n;++i)
			if (!vis[i])
		{
				for (j=0;j<(int)v[i].size();++j)
				{
						if (!vis[v[i][j]]) break;
				}
				break;
		}
		ga=i,gb=v[i][j]; gtm[gb]=1;
		dfs_even(ga);
		x_next[++x_next[0]]=0; 
		sort(x_next+1,x_next+x_next[0]+1); 
		int id=(x_next[0]+1)/2;
		for (i=1;i<=x_next[0];++i) ans+=abs(x_next[id]-x_next[i]);
		if (size[0][ga]==size[1][ga])
		cout<<ans<<endl;
		else puts("-1");
}
void dfs_odd(int x)
{
		int i;
		size[now[x]][x]++;
		for (i=0;i<(int)v[x].size();++i)
		{
				int p=v[x][i];
				if ((x==ga&&p==gb)||(x==gb&&p==ga)) continue;
				if (fa[x]==p) continue;
				fa[p]=x;
				now[p]=now[x]^1;
				dfs_odd(p);
				size[0][x]+=size[0][p];
				size[1][x]+=size[1][p];
		}	
}
void work_odd_cycle()
{
		for (i=1;i<=n;++i)
		if (!vis[i])
		{
				for (j=0;j<(int)v[i].size();++j)
				{
						if (!vis[v[i][j]]) break;
				}
				break;
		}
		ga=i,gb=v[i][j];
		dfs_odd(ga);	
		if (abs(size[0][ga]-size[1][ga])&1) 
		{
			puts("-1");
			return;
		}
		else if (size[0][ga]>=size[1][ga])
		{
				int l=(size[0][ga]-size[1][ga])>>1;
				ans+=l;
				size[1][ga]+=l,size[1][gb]+=l;
				for (i=fa[gb];i;i=fa[i]) size[1][i]+=l;
		}
		else 
		{
				int l=(size[1][ga]-size[0][ga])>>1;
				ans+=l;
				size[0][ga]+=l,size[0][gb]+=l;
				for (i=fa[gb];i;i=fa[i]) size[0][i]+=l;
		}
		for (i=1;i<=n;++i) 
			if (i!=ga)
			ans+=abs(size[0][i]-size[1][i]);
		cout<<ans<<endl;
}
void workb()
{
		x=find_cycle_length();
		if (x&1) work_odd_cycle();
		else work_even_cycle();
}
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;++i)
	{
			scanf("%d%d",&x,&y);
			v[x].pb(y); v[y].pb(x); 
	}
	if (m==n-1) worka();
	else workb(); 
}

Submission Info

Compile Error

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

Judge Result