Submission #1691086

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;

#define all(x) x.begin(), x.end()

#define int long long

vector<int> g[101010];
int black, white, type, s, t, cnt;
int color[101010];
bool include_s[101010], include_t[101010];
vector<long long> flow;
long long ans;

void coloring(int v, int prev, int c) {
        color[v] = c;
        if (c & 1) black ++;
        else white ++;
        for (auto u : g[v]) if (u != prev) {
                if (color[u] == -1) { 
                        coloring(u, v, 1 - c);
                } else {
                        s = v, t = u;
                        if (color[u] == 1 - c) type = 1;
                        else type = 2;
                }
        }
}

pair<int, int> dfs(int v, int prev, int d) {
        int b = 0, w = 0;
        include_s[v] = include_t[v] = false;
        include_s[v] |= v == s;
        include_t[v] |= v == t;
        for (auto u : g[v]) if (u != prev) {
                pair<int, int> get = dfs(u, v, d + 1);
                include_s[v] |= include_s[u];
                include_t[v] |= include_t[u];
                b += get.first;
                w += get.second;
        }
        if (d & 1) b ++;
        else w ++;
        if (type == 2 && (v == s || v == t)) b -= cnt;
        if (type == 1 && 
            ((include_s[v] && include_t[v]) || (!include_s[v] && !include_t[v]))) {
                flow.push_back(b - w);
        } else {
                ans += abs(b - w);
        }
        return make_pair(b, w);
}

signed main() {
        int n, m;
        scanf("%lld%lld", &n, &m);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%lld%lld", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        black = white = type = 0;
        memset(color, -1, sizeof color);
        coloring(0, -1, 0);
        if ((type == 0 && black != white) ||
            (type == 1 && black != white) ||
            (type == 2 && black % 2 != white % 2)) {
                puts("-1");
                return 0;
        }
        if (type != 0) {
                g[s].erase(remove(all(g[s]), t), g[s].end());
                g[t].erase(remove(all(g[t]), s), g[t].end());
        }
        cnt = (black - white) / 2;
        dfs(0, -1, 0);
        if (type == 2) ans += abs(cnt);
        if (type == 1) {
                int lb = -101010, ub = 101010;
                while (ub - lb > 4) {
                        int left = (lb * 2 + ub) / 3;
                        int right = (lb + ub * 2) / 3;
                        int left_ans = 0, right_ans = 0;
                        for (auto f : flow) {
                                left_ans += abs(left + f);
                                right_ans += abs(right + f);
                        }
                        if (left_ans < right_ans) ub = right;
                        else lb = left;
                }
                long long res = 0x3f3f3f3f;
                for (int i = lb - 10; i < lb + 10; i ++) {
                        long long sum = 0;
                        for (auto f : flow) sum += abs(i + f);
                        sum += abs(i); //self
                        res = min(res, sum);
                }
                ans += res;
        }
        printf("%lld\n", ans);
        return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &n, &m);
                                  ^
./Main.cpp:59:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%lld%lld", &a, &b);
                                          ^

Judge Result