Submission #881734


Source Code Expand

#pragma comment(linker, "/STACK:102400000,102400000") 
#pragma warning(disable:4996)
#include <fstream>
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define eps 1e-10
#define LL_INF 0x3fffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define pper(i,n,m) for(int i = n;i >= m; i--)
#define repp(i, n, m) for (int i = n; i <= m; i++)
#define rep(i, n, m) for (int i = n; i < m; i++)
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back

const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
const double PI = acos(-1.0);
ll po(ll a, ll b, ll mod) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1)res = res*a%mod; a = a*a%mod; }return res; }
ll gcd(ll a, ll b) { if (a == 0) { return b; } else { return gcd(b%a, a); } }

ll res;
int n, m;
int p1, p2;
int num[2], col[maxn], vis[maxn], pre[maxn];
ll st[maxn], en[maxn];
vector<int>edge[maxn];
vector<int>cycle;

void dfs(int x, int fa,int co)
{
	vis[x] = 1;
	col[x] = co;
	num[co]++;
	for (int i = 0; i < edge[x].size(); i++)
	{
		int k = edge[x][i];
		if (vis[k])continue;
		if (k == fa)continue;
		if (x == p1 && k == p2)continue;
		if (x == p2 && k == p1)continue;
		dfs(k, x, 1 - co);
	}
}

void dfs2(int x, int fa)
{
	vis[x] = 1;
	for (int i = 0; i < edge[x].size(); i++)
	{
		int k = edge[x][i];
		if (vis[k])continue;
		if (k == fa)continue;
		if (x == p1 && k == p2)continue;
		if (x == p2 && k == p1)continue;
		dfs2(k, x);
		res += abs(st[k] - en[k]);
		st[x] += st[k];
		en[x] += en[k];
	}
	if (col[x])
	{
		st[x]++;
	}
	else
	{
		en[x]++;
	}
}

void dfs_cycle(int x, int fa)
{
	vis[x] = 1;
	pre[x] = fa;
	for (int i = 0; i < edge[x].size(); i++)
	{
		int k = edge[x][i];
		if (k == fa)continue;
		if (vis[k])
		{
			if (p1 == -1)
			{
				p1 = x;
				p2 = k;
			}
			return;
		}
		dfs_cycle(k, x);
	}
}

void build_cycle()
{
	for (int i = p1; i != -1; i = pre[i])
	{
		cycle.push_back(i);
		if (i == p2)
		{
			break;
		}
	}
}

ll cal(ll x)
{
	memset(st, 0, sizeof(st));
	memset(en, 0, sizeof(en));
	memset(vis, 0, sizeof(vis));
	st[p1] = x;
	en[p2] = x;
	res = 0;
	dfs2(1, -1);
	return res + abs(x);
}

void solve()
{
	scanf("%d%d", &n, &m);
	if (n % 2)
	{
		puts("-1");
		return;
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	p1 = p2 = -1;
	if (m == n - 1)
	{
		dfs(1, -1, 0);
		if (num[0] == num[1])
		{
			memset(vis, 0, sizeof(vis));
			res = 0;
			dfs2(1, -1);
		}
		else
		{
			res = -1;
		}
		printf("%lld\n", res);
	}
	else
	{
		memset(vis, 0, sizeof(vis));
		dfs(1, -1, 0);
		memset(vis, 0, sizeof(vis));
		dfs_cycle(1, -1);
		build_cycle();
		
		if (cycle.size() % 2 == 0)
		{
			if (num[0] != num[1])
			{
				puts("-1");
				return;
			}
			ll le = -(1e6 + 5), ri = 1e6 + 5;
			while (ri - le > 5)
			{
				ll mid = (ri + le) / 2;
				ll t1 = cal(mid);
				ll t2 = cal(mid + 1);

				if (t1 < t2)
				{
					ri = mid;
				}
				else
				{
					le = mid;
				}
			}
			ll ans = LL_INF;
			for (ll i = le; i <= ri; i++)
			{
				ans = min(ans, cal(i));
			}
			printf("%lld\n", ans);
		}
		else
		{
			memset(num, 0, sizeof(num));
			memset(vis, 0, sizeof(vis));
			dfs(p1, -1, 0);
			col[p2] = 0;
			if (num[1]>num[0])
			{
				en[p1] = en[p2] = (num[1] - num[0]) / 2;
			}
			else
			{
				st[p1] = st[p2] = (num[0] - num[1]) / 2;
			}
			res = 0;
			memset(vis, 0, sizeof(vis));
			dfs2(1, -1);
			printf("%lld", res + abs((num[0] - num[1]) / 2));
		}
	}
}

int main()
{
	solve();
	return 0;
}


Submission Info

Submission Time
Task F - Namori
User wangchong756
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 4035 Byte
Status AC
Exec Time 797 ms
Memory 16760 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:137: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:146: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 10 ms 3068 KB
0_01.txt AC 8 ms 2560 KB
0_02.txt AC 17 ms 4480 KB
0_03.txt AC 8 ms 2944 KB
1_00.txt AC 8 ms 2944 KB
1_01.txt AC 124 ms 15616 KB
1_02.txt AC 89 ms 10368 KB
1_03.txt AC 67 ms 8440 KB
1_04.txt AC 105 ms 11648 KB
1_05.txt AC 108 ms 11264 KB
1_06.txt AC 103 ms 11264 KB
1_07.txt AC 100 ms 10496 KB
1_08.txt AC 109 ms 11904 KB
1_09.txt AC 80 ms 8448 KB
1_10.txt AC 90 ms 8192 KB
1_11.txt AC 89 ms 8192 KB
1_12.txt AC 95 ms 8064 KB
1_13.txt AC 8 ms 2560 KB
1_14.txt AC 79 ms 6656 KB
1_15.txt AC 95 ms 8064 KB
1_16.txt AC 8 ms 2560 KB
1_17.txt AC 95 ms 8064 KB
2_00.txt AC 17 ms 4608 KB
2_01.txt AC 731 ms 16760 KB
2_02.txt AC 516 ms 12928 KB
2_03.txt AC 263 ms 8824 KB
2_04.txt AC 609 ms 12796 KB
2_05.txt AC 660 ms 12672 KB
2_06.txt AC 676 ms 12668 KB
2_07.txt AC 631 ms 12796 KB
2_08.txt AC 671 ms 12668 KB
2_09.txt AC 395 ms 8704 KB
2_10.txt AC 465 ms 8704 KB
2_11.txt AC 527 ms 8576 KB
2_12.txt AC 576 ms 8448 KB
2_13.txt AC 7 ms 2560 KB
2_14.txt AC 88 ms 7296 KB
2_15.txt AC 592 ms 8576 KB
2_16.txt AC 7 ms 2560 KB
2_17.txt AC 583 ms 8576 KB
2_18.txt AC 10 ms 2560 KB
2_19.txt AC 113 ms 13052 KB
2_20.txt AC 71 ms 8056 KB
2_21.txt AC 797 ms 16760 KB
2_22.txt AC 120 ms 12800 KB
2_23.txt AC 121 ms 12796 KB
2_24.txt AC 133 ms 12668 KB
2_25.txt AC 113 ms 12924 KB
2_26.txt AC 122 ms 12672 KB
2_27.txt AC 95 ms 8832 KB
2_28.txt AC 100 ms 8576 KB
2_29.txt AC 104 ms 8576 KB
2_30.txt AC 112 ms 8448 KB
2_31.txt AC 7 ms 2560 KB
2_32.txt AC 115 ms 8832 KB
2_33.txt AC 113 ms 8576 KB
2_34.txt AC 8 ms 2560 KB
2_35.txt AC 124 ms 8448 KB
2_36.txt AC 276 ms 8824 KB
2_37.txt AC 272 ms 8824 KB
2_38.txt AC 267 ms 8824 KB
2_39.txt AC 263 ms 8824 KB
2_40.txt AC 269 ms 8824 KB
2_41.txt AC 263 ms 8824 KB
2_42.txt AC 267 ms 8824 KB
2_43.txt AC 263 ms 8824 KB