Submission #1228720

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 100010;
struct node {
	int y, next;
}a[Maxn*2]; int first[Maxn], len;
void ins(int x, int y) {
	len++;
	a[len].y = y;
	a[len].next = first[x]; first[x] = len;
}
int n, m, bsum[Maxn], bs[Maxn], size[Maxn], ans;
int dfn[Maxn], id, co[Maxn], fzx, fzy;
int p[Maxn], pl;
bool state;
int _abs(int x) { return x < 0 ? -x : x; }
void dfs(int x, int fk) {
	dfn[x] = ++id; bsum[x] = co[x] == 1 ? 1 : 0; size[x] = 1;
	for(int k = first[x]; k; k = a[k].next){
		int y = a[k].y;
		if((k+1)/2 == (fk+1)/2) continue;
		if(dfn[y] == 0){
			co[y] = co[x]^1;
			dfs(y, k);
			if(state == false && dfn[y] <= dfn[fzx] && dfn[fzx] <= dfn[y]+size[y]-1 && (dfn[y] > dfn[fzy] || dfn[fzy] > dfn[y]+size[y]-1)) p[++pl] = 2*bsum[y]-size[y];
			else ans += _abs(size[y]-2*bsum[y]);
			bsum[x] += bsum[y];
			size[x] += size[y];
		} else {
			fzx = x; fzy = y;
			if(co[y] != co[x]) state = false;
		}
	}
}
void dfs2(int x, int fk) {
	dfn[x] = ++id; bsum[x] = co[x] == 1 ? 1 : 0; size[x] = 1;
	bs[x] = bsum[x];
	if(x == fzx || x == fzy) bs[x] += (n-2*bsum[0])/2;
	for(int k = first[x]; k; k = a[k].next){
		int y = a[k].y;
		if((k+1)/2 == (fk+1)/2) continue;
		if(dfn[y] == 0){
			co[y] = co[x]^1;
			dfs2(y, k);
			ans += _abs(size[y]-bsum[y]-bs[y]);
			bsum[x] += bsum[y];
			bs[x] += bs[y];
			size[x] += size[y];
		}
	}
}
void case1() {
	ans = 0;
	memset(dfn, 0, sizeof(dfn)); id = 0;
	state = true; dfs(1, 0);
	if(bsum[1]*2 != n){ printf("-1\n"); return; }
	printf("%d\n", ans);
}
void case2() {
	if(bsum[1]%2 != (n-bsum[1])%2){ printf("-1\n"); return; }
	bsum[0] = bsum[1]; ans = 0;
	memset(dfn, 0, sizeof(dfn)); id = 0;
	dfs2(1, 0);
	printf("%d\n", ans+_abs(n-2*bsum[0])/2);
}
void case3() {
	if(bsum[1]*2 != n){ printf("-1\n"); return; }
	sort(p+1, p+pl+1);
	int o;
	for(int i = 1; i <= pl; i++) p[i] <<= 1;
	if(pl%2 == 0) o = (p[pl>>1]+p[(pl>>1)+1])>>1;
	else o = p[(pl+1)>>1];
	for(int i = 1; i <= pl; i++) ans += _abs(p[i]-o)>>1;
	ans += _abs(o)>>1;
	printf("%d\n", ans);
}
int main() {
	int i, j, k, T;
	T=1;
	while(T--){
		scanf("%d%d", &n, &m);
		len = 0; memset(first, 0, sizeof(first));
		for(i = 1; i <= m; i++){
			int x, y;
			scanf("%d%d", &x, &y);
			ins(x, y); ins(y, x);
		}
		if(n == m+1) case1();
		else {
			memset(dfn, 0, sizeof(dfn)); id = 0;
			state = true; pl = 0; ans = 0; dfs(1, 0);
			if(state == 1) case2();
			else case3();
		}
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result