Submission #869224

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
ll ans = 0;
int was[120000];
vector<int> eds[120000];
int cl[120000];
int cc[120000][2];
int a[120000];
int n, m;

void dfs1(int v, int c) {
	was[v] = 1;
	cl[v] = c;
	++cc[v][c];
	for (int u: eds[v]) {
		if (!was[u]) {
			dfs1(u, c^1);
			cc[v][0] += cc[u][0];
			cc[v][1] += cc[u][1];
		}
	}
	ans += abs(cc[v][0] - cc[v][1]);
}

vector<int> vv;
vector<int> st;

int dfs2(int v, int fr) {
	st.push_back(v);
	was[v] = 1;
	for (int u: eds[v]) {
		if (u == fr)
			continue;
		if (!was[u]) {
			if (dfs2(u, v))
				return 1;
		}
		else {
			while (st.back() != u)
				vv.push_back(st.back()), st.pop_back();
			vv.push_back(u);
			return 1;
		}
	}
	st.pop_back();
	return 0;
}

ll get(int x) {
	ll ans = 0;
	ll now = x;
	for (int i = 0; i < n; ++i) {
		now += a[i];
		ans += abs(now);
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	if (n % 2 == 1) {
		cout << -1 << "\n";
		return 0;
	}
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a;
		--b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	if (m == n - 1) {
		dfs1(0, 0);
		if (cc[0][0] != cc[0][1]) {
			cout << -1 << "\n";
		}
		else {
			cout << ans << "\n";
		}
	}
	else {
		dfs2(0, -1);
		memset(was, 0, sizeof(was));
		for (int i: vv)
			was[i] = 1;
		for (int i = 0; i < (int)vv.size(); ++i) {
			dfs1(vv[i], i % 2);
			a[i] = cc[vv[i]][0] - cc[vv[i]][1];
			ans -= abs(a[i]);
		}
		int sum = 0;
		for (int i = 0; i < (int)vv.size(); ++i)
			sum += a[i];
		n = vv.size();
		if ((int)vv.size() % 2 == 0) {
			if (sum != 0) {
				cout << -1 << "\n";
				return 0;
			}
			int lb = -120000;
			int rb = 120000;
			while (rb - lb > 3) {
				int m1 = lb + (rb - lb) / 3;
				int m2 = m1 + (rb - lb) / 3;
				if (get(m1) > get(m2))
					lb = m1;
				else
					rb = m2;
			}
			ll aans = 1e11;
			for (int j = lb; j <= rb; ++j)
				aans = min(aans, get(j));
			cout << ans + aans << "\n";
		}
		else {
			sum /= 2;
			ans += abs(sum);
			a[0] -= sum;
			a[n - 1] -= sum;
			cout << ans + get(0) << "\n";
		}
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result