Submission #1815397


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

#define A first
#define B second

const int MAXN = 1e5+5;

ll n, m, ans;
vector<int> g[MAXN];
bool isc[MAXN];
int deg[MAXN];
int p[MAXN];
vector<int> gg[MAXN];
vector<int> c, d;

pii dfs(int v, int f = -1) {
	pii tot = pii(0, 0);
	for (int u : g[v]) {
		if (isc[u] || u == f)
			continue;
		pii t = dfs(u, v);
		tot.A += t.A;
		tot.B += t.B;
	}

	if (tot.A >= tot.B)
		tot.A -= tot.B, tot.B = 0;
	else
		tot.B -= tot.A, tot.A = 0;

	if (tot.B >= 1)
		tot.B--;
	else
		tot.A++;

	if (!isc[v])
		ans += (tot.A + tot.B);
	swap(tot.A, tot.B);
	return tot;
}

void findc() {
	set<pii> s;
	for (int i = 0; i < n; ++i) {
		deg[i] = g[i].size();
		s.insert(pii(deg[i], i));
		// cout << i << ' ' << deg[i] << endl;
	}

	while (!s.empty()) {
		pii t = (*s.begin());
		// cout << t.B << endl;
		if (t.A == 2)
			break;
		s.erase(t);
		for (int u : g[t.B]) {
			s.erase(pii(deg[u], u));
			deg[u]--;
			if (deg[u] != 0)
				s.insert(pii(deg[u], u));
		}
	}

	for (pii t : s)
		isc[t.B] = 1;
}

void dfsc(int v, int f = -1) {
	d.push_back(v);
	if (gg[v][0] != f && gg[v][0] != d[0]) {
		dfsc(gg[v][0], v);
	} else if (gg[v][1] != f && gg[v][1] != d[0]) {
		dfsc(gg[v][1], v);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	if (m == n-1) {
		g[0].push_back(g[0][0]);
		g[g[0][0]].push_back(0);
	}

	if (n%2 == 1) {
		cout << "-1\n";
		return 0;
	}

	findc();

	for (int i = 0; i < n; ++i)
		if (isc[i]) {
			c.push_back(i);
			pii t = dfs(i, -1);
			p[i] = t.A - t.B;
		}

	for (int i : c)
		for (int j : g[i])
			if (isc[j])
				gg[i].push_back(j);

	dfsc(c[0]);
	c = d;

	if (c.size()%2 == 1) {
		ll x = 0;
		for (int i : c)
			x = -x + p[i];
		x /= 2;
		ans += abs(x);
		for (int i = 0; i < c.size()-1; ++i) {
			x = -x + p[c[i]];
			ans += abs(x);
		}

		cout << ans << endl;
	} else {
		ll s1 = 0, s2 = 0;
		for (int i = 0; i < c.size(); i += 2)
			s1 += p[c[i]], s2 += p[c[i+1]];
		if (s1 != s2) {
			cout << "-1\n";
			return 0;
		}

		vector<int> b;
		b.push_back(0);
		ll x = 0;

		for (int i = 0; i < c.size()-1; ++i) {
			x = -x + p[c[i]];
			if (i%2 == 0)
				b.push_back(-x);
			else
				b.push_back(x);
		}

		sort(b.begin(), b.end());
		for (int i = 0; i < c.size()/2; ++i)
			ans += b[i+c.size()/2] - b[i];
		cout << ans << endl;
	}
}

Submission Info

Submission Time
Task F - Namori
User desert97
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 2593 Byte
Status AC
Exec Time 187 ms
Memory 22784 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 1500 / 1500 700 / 700
Status
AC × 4
AC × 20
AC × 66
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
Subtask1 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt
Case Name Status Exec Time Memory
0_00.txt AC 3 ms 5760 KB
0_01.txt AC 3 ms 5760 KB
0_02.txt AC 3 ms 5760 KB
0_03.txt AC 3 ms 5760 KB
1_00.txt AC 3 ms 5760 KB
1_01.txt AC 187 ms 22784 KB
1_02.txt AC 130 ms 17536 KB
1_03.txt AC 187 ms 15608 KB
1_04.txt AC 160 ms 18816 KB
1_05.txt AC 155 ms 18432 KB
1_06.txt AC 160 ms 18432 KB
1_07.txt AC 156 ms 17536 KB
1_08.txt AC 155 ms 19072 KB
1_09.txt AC 144 ms 15488 KB
1_10.txt AC 148 ms 15360 KB
1_11.txt AC 151 ms 15360 KB
1_12.txt AC 162 ms 15232 KB
1_13.txt AC 73 ms 8960 KB
1_14.txt AC 158 ms 15360 KB
1_15.txt AC 157 ms 15232 KB
1_16.txt AC 74 ms 8960 KB
1_17.txt AC 160 ms 15232 KB
2_00.txt AC 3 ms 5760 KB
2_01.txt AC 130 ms 16784 KB
2_02.txt AC 117 ms 15360 KB
2_03.txt AC 156 ms 15608 KB
2_04.txt AC 141 ms 15360 KB
2_05.txt AC 142 ms 15232 KB
2_06.txt AC 141 ms 15232 KB
2_07.txt AC 140 ms 15360 KB
2_08.txt AC 144 ms 15232 KB
2_09.txt AC 142 ms 15488 KB
2_10.txt AC 149 ms 15360 KB
2_11.txt AC 159 ms 15360 KB
2_12.txt AC 160 ms 15232 KB
2_13.txt AC 75 ms 8960 KB
2_14.txt AC 168 ms 15232 KB
2_15.txt AC 163 ms 15232 KB
2_16.txt AC 73 ms 8960 KB
2_17.txt AC 162 ms 15232 KB
2_18.txt AC 3 ms 5760 KB
2_19.txt AC 114 ms 15356 KB
2_20.txt AC 166 ms 15608 KB
2_21.txt AC 132 ms 16784 KB
2_22.txt AC 137 ms 15360 KB
2_23.txt AC 132 ms 15360 KB
2_24.txt AC 139 ms 15232 KB
2_25.txt AC 139 ms 15488 KB
2_26.txt AC 138 ms 15232 KB
2_27.txt AC 154 ms 15616 KB
2_28.txt AC 158 ms 15360 KB
2_29.txt AC 147 ms 15360 KB
2_30.txt AC 159 ms 15232 KB
2_31.txt AC 73 ms 8960 KB
2_32.txt AC 159 ms 15232 KB
2_33.txt AC 163 ms 15232 KB
2_34.txt AC 73 ms 8960 KB
2_35.txt AC 160 ms 15232 KB
2_36.txt AC 157 ms 15608 KB
2_37.txt AC 163 ms 15608 KB
2_38.txt AC 158 ms 15608 KB
2_39.txt AC 161 ms 15608 KB
2_40.txt AC 164 ms 15608 KB
2_41.txt AC 167 ms 15608 KB
2_42.txt AC 164 ms 15608 KB
2_43.txt AC 162 ms 15608 KB