Submission #1108456
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <cmath> using namespace std; #define mp make_pair #define pb push_back #define ll long long #define maxN 100011 int n, m, x, y, i; vector<int> list[maxN]; int col[maxN]; bool us[maxN]; ll in[maxN], sum[maxN]; vector<int> way, cyc; ll abss(ll a) { if (a < 0) return -a; return a; } void dfs(int node) { us[node] = true; for (auto to : list[node]) { if (us[to]) continue; col[to] = col[node] ^ 1; dfs(to); } } ll solve_simple(int node, int root) { ll ans = 0; sum[node] = in[node]; for (auto to : list[node]) { if (to == root) continue; ans += solve_simple(to, node); sum[node] += sum[to]; } return ans + abss(sum[node]); } void find_cyc(int node) { if (!cyc.empty()) return; way.pb(node); us[node] = true; for (auto to : list[node]) { if (way.size() >= 2) if (to == way[way.size() - 2]) continue; if (us[to]) { int i; cyc.pb(to); while (way.back() != to) { cyc.pb(way.back()); way.pop_back(); } return ; } else { find_cyc(to); if (!cyc.empty()) return; } } us[node] = false; way.pop_back(); } void rm_edge(int x, int y) { for (int i = 0; i < list[x].size(); i++) { if (list[x][i] == y) { list[x][i] = list[x].back(); break; } } swap(x, y); for (int i = 0; i < list[x].size(); i++) { if (list[x][i] == y) { list[x][i] = list[x].back(); break; } } list[x].pop_back(); list[y].pop_back(); } ll check(int u, int v, ll mid) { int i; for (i = 1; i <= n; i++) in[i] = (col[i] ? 1 : -1); in[u] += mid; in[v] -= mid; ll ans = solve_simple(1, 0); in[u] -= mid; in[v] += mid; return ans; } void solve_even() { int u, v; ll ans; u = cyc[0]; v = cyc[1]; rm_edge(u, v); for (i = 1; i <= n; i++) in[i] = (col[i] ? 1 : -1); ans = solve_simple(1, 0); if (sum[1] != 0) { printf("-1"); exit(0); } ll l = -n; ll r = n; while (r - l + 1 > 10) { ll mid1 = (2 * l + r) / 3; ll mid2 = (l + 2 * r) / 3; ll ans1 = check(u, v, mid1) + abss(mid1); ll ans2 = check(u, v, mid2) + abss(mid2); if (ans1 <= ans2) r = mid2; else l = mid1; } ans = 1LL << 60; for (int i = l; i <= r; i++) ans = min(ans, check(u, v, i) + abss(i)); printf("%lld", ans); } void solve_odd() { int i, u, v; cyc.pb(cyc[0]); for (i = 0; i + 1 < cyc.size(); i++) { if (col[cyc[i]] != col[cyc[i + 1]]) continue; u = cyc[i]; v = cyc[i + 1]; break; } rm_edge(u, v); for (i = 1; i <= n; i++) in[i] = (col[i] ? 1 : -1); ll ans = solve_simple(1, 0); if (abss(sum[1]) % 2 == 1) { printf("-1"); exit(0); } for (i = 1; i <= n; i++) in[i] = (col[i] ? 1 : -1); in[u] -= sum[1] / 2; in[v] -= sum[1] / 2; ll add = sum[1] / 2; ans = solve_simple(1, 0); printf("%lld", ans + abss(add)); } int main() { // freopen("test.in","r",stdin); scanf("%d%d", &n, &m); for (i = 1; i <= m; i++) { scanf("%d%d", &x, &y); list[x].pb(y); list[y].pb(x); } dfs(1); if (n - 1 == m) { for (i = 1; i <= n; i++) in[i] = (col[i] ? 1 : -1); ll ans = solve_simple(1, 0); if (sum[1] != 0) printf("-1"); else printf("%lld", ans); } else { memset(us, 0, sizeof(us)); find_cyc(1); if (cyc.size() % 2 == 0) solve_even(); else solve_odd(); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori |
User | atatomir |
Language | C++14 (GCC 5.4.1) |
Score | 2200 |
Code Size | 4205 Byte |
Status | AC |
Exec Time | 410 ms |
Memory | 16504 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:196:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &n, &m); ^ ./Main.cpp:198:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &x, &y); ^
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 | 5 ms | 2560 KB |
0_01.txt | AC | 5 ms | 2560 KB |
0_02.txt | AC | 5 ms | 2688 KB |
0_03.txt | AC | 5 ms | 2688 KB |
1_00.txt | AC | 5 ms | 2560 KB |
1_01.txt | AC | 61 ms | 15360 KB |
1_02.txt | AC | 48 ms | 10112 KB |
1_03.txt | AC | 38 ms | 8184 KB |
1_04.txt | AC | 56 ms | 11392 KB |
1_05.txt | AC | 55 ms | 11008 KB |
1_06.txt | AC | 55 ms | 11008 KB |
1_07.txt | AC | 52 ms | 10112 KB |
1_08.txt | AC | 55 ms | 11648 KB |
1_09.txt | AC | 44 ms | 8064 KB |
1_10.txt | AC | 46 ms | 7936 KB |
1_11.txt | AC | 49 ms | 7936 KB |
1_12.txt | AC | 51 ms | 7808 KB |
1_13.txt | AC | 51 ms | 8448 KB |
1_14.txt | AC | 51 ms | 7936 KB |
1_15.txt | AC | 50 ms | 7808 KB |
1_16.txt | AC | 50 ms | 7808 KB |
1_17.txt | AC | 50 ms | 7808 KB |
2_00.txt | AC | 5 ms | 2688 KB |
2_01.txt | AC | 400 ms | 16504 KB |
2_02.txt | AC | 267 ms | 12412 KB |
2_03.txt | AC | 124 ms | 8184 KB |
2_04.txt | AC | 318 ms | 12284 KB |
2_05.txt | AC | 343 ms | 12284 KB |
2_06.txt | AC | 362 ms | 12156 KB |
2_07.txt | AC | 343 ms | 12284 KB |
2_08.txt | AC | 355 ms | 12156 KB |
2_09.txt | AC | 202 ms | 8064 KB |
2_10.txt | AC | 248 ms | 7936 KB |
2_11.txt | AC | 294 ms | 7936 KB |
2_12.txt | AC | 326 ms | 7808 KB |
2_13.txt | AC | 60 ms | 11772 KB |
2_14.txt | AC | 53 ms | 8192 KB |
2_15.txt | AC | 330 ms | 7808 KB |
2_16.txt | AC | 52 ms | 7808 KB |
2_17.txt | AC | 326 ms | 7808 KB |
2_18.txt | AC | 5 ms | 2688 KB |
2_19.txt | AC | 58 ms | 12540 KB |
2_20.txt | AC | 40 ms | 8184 KB |
2_21.txt | AC | 410 ms | 16504 KB |
2_22.txt | AC | 62 ms | 12412 KB |
2_23.txt | AC | 66 ms | 12284 KB |
2_24.txt | AC | 66 ms | 12156 KB |
2_25.txt | AC | 62 ms | 12412 KB |
2_26.txt | AC | 65 ms | 12284 KB |
2_27.txt | AC | 50 ms | 8192 KB |
2_28.txt | AC | 52 ms | 7936 KB |
2_29.txt | AC | 55 ms | 7936 KB |
2_30.txt | AC | 59 ms | 7808 KB |
2_31.txt | AC | 58 ms | 10748 KB |
2_32.txt | AC | 58 ms | 8064 KB |
2_33.txt | AC | 57 ms | 7808 KB |
2_34.txt | AC | 52 ms | 7808 KB |
2_35.txt | AC | 71 ms | 7808 KB |
2_36.txt | AC | 127 ms | 8184 KB |
2_37.txt | AC | 124 ms | 8184 KB |
2_38.txt | AC | 125 ms | 8184 KB |
2_39.txt | AC | 125 ms | 8184 KB |
2_40.txt | AC | 126 ms | 8184 KB |
2_41.txt | AC | 124 ms | 8184 KB |
2_42.txt | AC | 125 ms | 8184 KB |
2_43.txt | AC | 123 ms | 8184 KB |