Submission #901350


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], n, m, v[N];
long long cnt[N][2];
vector<int> G[N];
int p1, p2, len;
long long dfs(int x, int p = 0, int d = 0) {
	++ cnt[x][d & 1];
	long long res = 0;
	for (int u : G[x]) {
		if (u == p) continue;
		if (x == p1 && u == p2) continue;
		if (x == p2 && u == p1) continue;
		res += dfs(u, x, d + 1);
		cnt[x][0] += cnt[u][0];
		cnt[x][1] += cnt[u][1];
		res += abs(cnt[u][0] - cnt[u][1]);
	}
	return res;
}
void dfs2(int x, int p = 0) {
	v[x] = v[p] + 1;
	for (int u : G[x]) {
		if (u == p) continue;
		if (v[u]) {
			p1 = x;
			p2 = u;
			len = v[x] - v[u] + 1;
		}
		else dfs2(u, x);
	}
}
long long calc(long long x) {
	memset(cnt, 0, sizeof(cnt));
	cnt[p1][0] += x;
	cnt[p2][1] += x;
	return dfs(1) + abs(x);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		a[i] = u, b[i] = v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	if (m == n - 1) {
		long long ans = dfs(1);
		if (cnt[1][0] != cnt[1][1]) return 0 * puts("-1");
		printf("%lld\n", ans);
	}
	else {
		dfs2(1);
		dfs(1);
		if (len & 1) {
			if (abs(cnt[1][0] - cnt[1][1]) & 1) return 0 * puts("-1");
			long long del = (cnt[1][0] - cnt[1][1]) / 2;
			memset(cnt, 0, sizeof(cnt));
			cnt[p1][0] -= del;
			cnt[p2][0] -= del;
			long long ans = dfs(1) + abs(del);
			printf("%lld\n", ans);
		}
		else {
			if (cnt[1][0] != cnt[1][1]) return 0 * puts("-1");
			long long l = - 1e9, r = 1e9, ans = 1e18;
			while (l + 10 <= r) {
				long long midl = (l + r) / 2;
				long long midr = (midl + r) / 2;
				long long res1 = calc(midl);
				long long res2 = calc(midr);
				ans = min(ans, res1);
				ans = min(ans, res2);
				if (res1 < res2) {
					r = midr - 1;
				}
				else {
					l = midl + 1;
				}
			}
			for (int i = l; i <= r; ++ i) ans = min(ans, calc(i));
			printf("%lld\n", ans);
		}
	}
}

Submission Info

Submission Time
Task F - Namori
User Akigeor
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 1988 Byte
Status AC
Exec Time 683 ms
Memory 16256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41: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:44: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

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 5 ms 2560 KB
0_01.txt AC 5 ms 2560 KB
0_02.txt AC 14 ms 4096 KB
0_03.txt AC 6 ms 4096 KB
1_00.txt AC 5 ms 2560 KB
1_01.txt AC 54 ms 15616 KB
1_02.txt AC 43 ms 10368 KB
1_03.txt AC 36 ms 8440 KB
1_04.txt AC 49 ms 11648 KB
1_05.txt AC 51 ms 11264 KB
1_06.txt AC 49 ms 11264 KB
1_07.txt AC 48 ms 10496 KB
1_08.txt AC 52 ms 11904 KB
1_09.txt AC 41 ms 8448 KB
1_10.txt AC 43 ms 8192 KB
1_11.txt AC 44 ms 8192 KB
1_12.txt AC 46 ms 8064 KB
1_13.txt AC 47 ms 8704 KB
1_14.txt AC 46 ms 8320 KB
1_15.txt AC 46 ms 8064 KB
1_16.txt AC 46 ms 8064 KB
1_17.txt AC 48 ms 8064 KB
2_00.txt AC 14 ms 4096 KB
2_01.txt AC 683 ms 16256 KB
2_02.txt AC 378 ms 12544 KB
2_03.txt AC 177 ms 8824 KB
2_04.txt AC 507 ms 12544 KB
2_05.txt AC 530 ms 12416 KB
2_06.txt AC 573 ms 12416 KB
2_07.txt AC 498 ms 12544 KB
2_08.txt AC 552 ms 12416 KB
2_09.txt AC 322 ms 8704 KB
2_10.txt AC 363 ms 8576 KB
2_11.txt AC 464 ms 8704 KB
2_12.txt AC 527 ms 8448 KB
2_13.txt AC 55 ms 11904 KB
2_14.txt AC 51 ms 8832 KB
2_15.txt AC 537 ms 8576 KB
2_16.txt AC 51 ms 8448 KB
2_17.txt AC 527 ms 8576 KB
2_18.txt AC 5 ms 2560 KB
2_19.txt AC 53 ms 12540 KB
2_20.txt AC 39 ms 8824 KB
2_21.txt AC 636 ms 16256 KB
2_22.txt AC 58 ms 12544 KB
2_23.txt AC 58 ms 12544 KB
2_24.txt AC 60 ms 12416 KB
2_25.txt AC 56 ms 12672 KB
2_26.txt AC 60 ms 12416 KB
2_27.txt AC 49 ms 8832 KB
2_28.txt AC 52 ms 8576 KB
2_29.txt AC 55 ms 8576 KB
2_30.txt AC 55 ms 8448 KB
2_31.txt AC 54 ms 11136 KB
2_32.txt AC 56 ms 8704 KB
2_33.txt AC 55 ms 8576 KB
2_34.txt AC 50 ms 8448 KB
2_35.txt AC 56 ms 8448 KB
2_36.txt AC 195 ms 8824 KB
2_37.txt AC 243 ms 8824 KB
2_38.txt AC 194 ms 8824 KB
2_39.txt AC 192 ms 8824 KB
2_40.txt AC 195 ms 8824 KB
2_41.txt AC 191 ms 8824 KB
2_42.txt AC 195 ms 8824 KB
2_43.txt AC 192 ms 8824 KB