Submission #3468103

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;

int n, m, E = 1, tot, ban;
int fir[N], nex[N << 1], arr[N << 1];
int incircle[N], pnt[N];
LL dp[N];

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y;
}

namespace Subtask_tree {
	LL sum = 0;
	
	void dfs(int x, int dep, int fa) {
		dp[x] += (dep & 1) ? 1 : -1;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa || (i >> 1) == (ban >> 1)) continue;
			dfs(arr[i], dep + 1, x);
			dp[x] += dp[arr[i]];
		}
		sum += abs(dp[x]);
	}
	
	int main() {
		dfs(1, 1, 0);
		if (dp[1] != 0) puts("-1");
		else printf("%lld\n", sum);
		return 0;
	}
}

namespace circle_init {
	int top, vis[N], st[N], instack[N];
	
	void getcircle(int x, int fa) {
		st[++top] = x;
		instack[x] = 1;
		vis[x] = 1;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa) continue;
			if (instack[arr[i]]) {
				incircle[arr[i]] = 1;
				pnt[++tot] = arr[i];
				for (int j = top; st[j] != arr[i]; --j) {
					incircle[st[j]] = 1;
					pnt[++tot] = st[j];
				}	
			}
			else if (!vis[arr[i]]) getcircle(arr[i], x);
		}
		--top;
		instack[x] = 0;
	}

	void getvalue(int x, int dep, int fa) {
		dp[x] = (dep & 1) ? 1 : -1;
		for (int i = fir[x]; i; i = nex[i]) {
			if (arr[i] == fa || incircle[arr[i]]) continue;
			getvalue(arr[i], dep + 1, x);
			dp[x] += dp[arr[i]];
		}
	}
	
}

namespace Subtask_even {
	LL res = 0, del[N]; // xi = x1 + del[i]
	
	int main() {
		int tmp = 0;
		for (int i = 1; i <= n; ++i) {
			if (!incircle[i]) res += abs(dp[i]);
			else tmp += dp[i];
		}
		if (tmp != 0) return 0 * puts("-1");
		for (int i = 2; i <= tot; ++i) {
			del[i] = del[i - 1] + dp[pnt[i]];
		}
		sort(del + 1, del + tot + 1);
		int mid = del[tot >> 1];
		for (int i = 1; i <= tot; ++i) {
			res += abs(del[i] - mid);
		}
		cout << res << endl;
		return 0;
	}
}

namespace Subtask_odd {
	int tmp, to;

	int main() {
		for (int i = fir[pnt[1]]; i; i = nex[i]) {
			if (incircle[arr[i]]) {
				ban = i;
				break;
			}
		}
		for (int i = 1; i <= tot; ++i)
			tmp += dp[pnt[i]];
		if (tmp & 1) return 0 * puts("-1");
		memset(dp, 0, sizeof dp);
		dp[pnt[1]] -= tmp / 2;
		dp[arr[ban]] -= tmp / 2;
		Subtask_tree::dfs(pnt[1], 1, 0);
		cout << Subtask_tree::sum + abs(tmp / 2) << endl;
		return 0;
 	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Add_Edge(x, y);
		Add_Edge(y, x);
	}
	if (m == n - 1) return Subtask_tree::main();
	circle_init::getcircle(1, 0);
	for (int i = 1; i <= tot; ++i) {
		circle_init::getvalue(pnt[i], i & 1, 0);
	}
	if (~tot & 1) return Subtask_even::main();
	else return Subtask_odd::main();
}

Submission Info

Compile Error

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

Judge Result