Submission #1629266

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}
#define SZ 666666
int n,m,ea=0,eb=0,ff[SZ]; Edg
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
int col[SZ],su[SZ],sz[SZ],dep[SZ],hb[SZ];
void dfs(int x,int f=0)
{
	col[x]=col[f]^1; su[x]=col[x]; sz[x]=1;
	dep[x]=dep[f]+1; hb[x]=(x==eb);
	for esb(x,e,b)
		if(b!=f) dfs(b,x),su[x]+=su[b],
		sz[x]+=sz[b],hb[x]|=hb[b];
}
int main()
{
	scanf("%d%d",&n,&m); ea=1;
	for(int i=1;i<=m;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		int ga=gf(a),gb=gf(b);
		if(ga^gb) adde(a,b),ff[ga]=gb;
		else ea=a,eb=b;
	}
	dfs(ea);
	if(m==n-1)
	{
		if(su[ea]!=n-su[ea])
		{
			puts("-1");
			return 0;
		}
		ll ans=0;
		for(int i=1;i<=n;++i) if(i!=ea)
			ans+=abs(sz[i]-su[i]-su[i]);
		printf("%lld\n",ans);
		return 0;
	}
	int cl=dep[eb];
	if(cl%2==0)
	{
		if(su[ea]!=n-su[ea])
		{
			puts("-1");
			return 0;
		}
		vector<int> v; ll ans=0;
		for(int i=1;i<=n;++i) if(i!=ea)
		{
			int g=sz[i]-su[i]-su[i];
			if(hb[i]) v.pb(g);
			else ans+=abs(g);
		}
		v.pb(0);
		sort(v.begin(),v.end());
		int s=v[v.size()/2];
		for(int i=0;i<v.size();++i)
			ans+=abs(v[i]-s);
		printf("%lld\n",ans);
	}
	else
	{
		int c=su[ea]-n+su[ea];
		if(c&1)
		{
			puts("-1");
			return 0;
		}
		c/=2; ll ans=abs(c);
		for(int i=1;i<=n;++i) if(i!=ea)
			ans+=abs(sz[i]-su[i]-su[i]+(hb[i]?c:0));
		printf("%lld\n",ans);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m); ea=1;
                     ^
./Main.cpp:52:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^

Judge Result