Submission #1691938

---

Source Code Expand

#include <bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define pb push_back

using namespace std;

const int N = 100010;

int n, m, col[N];
vector<int> G[N];

int banu, banv;

bool DFS_bipartite(int o){
	for(int v : G[o]){
		if((o == banu && v == banv) || (o == banv && v == banu)) continue;
		if(!col[v]){
			col[v] = 3 - col[o];
			if(!DFS_bipartite(v)) return false;
		}
		else if(col[o] == col[v]) return false;
	}
	return true;
}

bool vis[N];
int stk[N], top;
int cycle[N], c;

void DFS_cycle(int o, int f){
	vis[o] = true;
	stk[++top] = o;
	for(int v : G[o]){
		if(v == f) continue;
		if(!vis[v]) DFS_cycle(v, o);
		else if(!c){
			Forr(i, top, 1){
				cycle[++c] = stk[i];
				if(stk[i] == v) break;
			}
		}
	}
	--top;
}

int szx[N], szy[N];

int DFS_work(int o, int f){
	szx[o] += col[o] == 1;
	szy[o] += col[o] == 2;
	int ret = 0;
	for(int v : G[o]){
		if((o == banu && v == banv) || (o == banv && v == banu)) continue;
		if(v == f) continue;
		ret += DFS_work(v, o);
		szx[o] += szx[v], szy[o] += szy[v];
	}
	return ret + abs(szx[o] - szy[o]);
}

int calc(int x){
	memset(szx, 0, sizeof szx), memset(szy, 0, sizeof szy);
	szx[banu] += x, szx[banv] -= x;
	return DFS_work(1, 0) + abs(x);
}

int main(){
	scanf("%d%d", &n, &m);
	For(i, 1, m){
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v), G[v].pb(u);
	}
	
	col[1] = 1;
	bool bipart = DFS_bipartite(1);
	DFS_cycle(1, 0);
	
//	cerr << "cycle length = " << c << endl
//		 << "bipart = " << bipart << endl;

	if(!c){
		int ans = DFS_work(1, 0);
		if(szx[1] != szy[1]) puts("-1");
		else printf("%d\n", ans);
	}
	else if(bipart){
		banu = cycle[1], banv = cycle[2];

		DFS_work(1, 0);
		if(szx[1] != szy[1]){
			puts("-1");
			return 0;
		}

		int L = -n, R = n;
		while(L < R){
			int m1 = L + (R - L) / 3, m2 = R - (R - L) / 3;
			if(calc(m1) > calc(m2)) L = m1 + 1;
			else R = m2 - 1;
		}

		printf("%d\n", calc(L));
	}
	else{
		banu = cycle[1], banv = cycle[2];
		memset(col, 0, sizeof col);

		col[1] = 1;
		assert(DFS_bipartite(1));
		
		DFS_work(1, 0);
		int d = szx[1] - szy[1];
		if(d % 2){
			puts("-1");
			return 0;
		}

		memset(szx, 0, sizeof szx), memset(szy, 0, sizeof szy);
		szy[banu] += d / 2, szy[banv] += d / 2;
		printf("%d\n", DFS_work(1, 0) + abs(d / 2));
	}

	return 0;
}

Submission Info

Compile Error

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

Judge Result