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 |
|
|
|
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 |