Submission #869030

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int n,m,u,v,q[N],d[N],od[N];
ll ret;
VI e[N],cyc;
int dfs(int u,int f,int p) {
	int par=(p==0)?1:-1;
	for (auto v:e[u]) {
		if (v==f||d[v]!=1) continue;
		par+=dfs(v,u,p^1);
	}
	if (f!=0) ret+=abs(par);
	return par;
}
void dfs2(int u) {
	d[u]=0; cyc.pb(u);
	for (auto v:e[u]) if (d[v]==2) {
		dfs2(v);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	if (n-1==m) {
		rep(i,0,m) {
			scanf("%d%d",&u,&v);
			e[u].pb(v); e[v].pb(u);
		}
		rep(i,1,n+1) d[i]=1;
		int c=dfs(1,0,0);
		if (c!=0) {
			puts("-1");
		} else {
			printf("%lld\n",ret);
		}		
	} else {
		rep(i,0,m) {
			scanf("%d%d",&u,&v);
			e[u].pb(v); e[v].pb(u);
			d[u]++; d[v]++;
		}
		int t=0;
		rep(i,1,n+1) if (d[i]==1) {
			q[t++]=i;
		}
		rep(i,0,t) {
			int u=q[i];
			for (auto v:e[u]) {
				if (d[v]==1) continue;
				--d[v];
				if (d[v]==1) q[t++]=v;
			}
		}
		int rt=0;
		rep(i,1,n+1) if (d[i]==2) {
			rt=i;
			break;
		}
		dfs2(rt);
		m=SZ(cyc);
		rep(i,0,m) {
			od[i]=dfs(cyc[i],0,0);
		}
		if (m%2==0) {
			rep(i,0,m) if (i%2==1) od[i]*=-1;
			ll s=0;
			VI v;
			rep(i,0,m) {
				v.pb(s);
				s+=od[i];
			}
			if (s!=0) {
				puts("-1");
				return 0;
			}
			sort(all(v));
			rep(i,0,m/2) ret+=v[i+m/2]-v[i];
			printf("%lld\n",ret);
		} else {
			ll s=0;
			rep(i,0,m) s+=od[i];
			if (s%2!=0) {
				puts("-1");
				return 0;
			}
			s/=2;
			for (int i=1;i<m;i+=2) s-=od[i];
			ll c=s;
			rep(i,0,m) {
				ret+=max(s,-s);
				s=od[i]-s;
			}
			assert(s==c);
			printf("%lld\n",ret);
		}
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46: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:49:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&u,&v);
                       ^
./Main.cpp:61:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&u,&v);
                       ^

Judge Result