Submission #2560871
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; for (int i = 1; i <= n; ++i) dfs1(1, 0); 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 | F - Namori |
User | QQ_kotori |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2951 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:95:37: error: ‘i’ was not declared in this scope ans += abs(size[i]); ^