Submission #2560936
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10;
struct Edge {
int v, n;
} e[MAXN << 1];
int G[MAXN], edgeCnt;
void _add_edge(int u, int v)
{
e[++edgeCnt].n = G[u];
G[u] = edgeCnt;
e[edgeCnt].v = v;
}
void add_edge(int u, int v)
{
_add_edge(u, v);
_add_edge(v, u);
}
int n, m;
int f[MAXN];
int g[MAXN];
int h[MAXN];
int size[MAXN];
bool vis[MAXN];
int foo, bar;
void dfs1(int u, int fa)
{
size[u] = f[u] ? -1 : 1;
size[u] += f[u] ? -h[u] : h[u];
for (int i = G[u]; i; i = e[i].n)
if (e[i].v != fa) {
if (u == bar && e[i].v == foo
|| u == foo && e[i].v == bar) {
continue;
}
f[e[i].v] = f[u] ^ 1;
dfs1(e[i].v, u);
size[u] += size[e[i].v];
g[u] += g[e[i].v];
}
}
bool dfs2(int u, int fa)
{
if (vis[u])
return false;
vis[u] = true;
for (int i = G[u]; i; i = e[i].n)
if (e[i].v != fa) {
if (!dfs2(e[i].v, u))
foo = u, bar = e[i].v;
}
return true;
}
int main()
{
// freopen("sapphire.in", "r", stdin);
// freopen("sapphire.out", "w", stdout);
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
if (m == n - 1) {
dfs1(1, -1);
long long ans = 0;
for (int i = 1; i <= n; ++i)
ans += abs(size[i]);
cout << (size[1] == 0 ? ans : -1) << endl;
} else {
dfs2(1, 0);
g[foo] = 1;
g[bar] = -1;
dfs1(1, 0);
long long ans = 0;
if (f[foo] == f[bar]) {
if (abs(size[1]) & 1)
cout << "-1\n";
else {
ans += abs(size[1]) / 2;
h[foo] = h[bar] = ans; dfs1(1, 0);
for (int i = 1; i <= n; ++i)
ans += abs(size[i]);
cout << ans << endl;
}
} else {
if (size[1] != 0)
cout << "-1\n";
else {
static int a[MAXN], cnt = 0;
for (int i = 1; i <= n; ++i) {
if (g[i] == 0) {
ans += abs(size[i]);
} else {
a[++cnt] = -g[i] * size[i];
}
}
nth_element(a + 1, a + (1 + cnt) / 2, a + cnt + 1);
int temp = a[(1 + cnt) / 2];
for (int i = 1; i <= n; ++i)
if (g[i] != 0) {
ans += abs(size[i] + g[i] * temp);
}
ans += (f[foo] ^ 1 ? -1 : 1) * temp;
cout << ans << endl;
}
}
}
}
Submission Info
Submission Time |
|
Task |
A - Divide a Cuboid |
User |
QQ_kotori |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2962 Byte |
Status |
RE |
Exec Time |
98 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
WA |
1 ms |
256 KB |
0_01.txt |
WA |
1 ms |
256 KB |
0_02.txt |
WA |
1 ms |
256 KB |
1_00.txt |
RE |
97 ms |
256 KB |
1_01.txt |
RE |
96 ms |
256 KB |
1_02.txt |
RE |
98 ms |
256 KB |
1_03.txt |
RE |
97 ms |
256 KB |
1_04.txt |
RE |
97 ms |
256 KB |
1_05.txt |
RE |
96 ms |
256 KB |