Submission #1690910

---

Source Code Expand

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

#define int long long

vector<int> g[101010];
int color[101010];
int black_all, white_all, type, start, goal;
long long ans;

bool in_start[101010], in_goal[101010];
vector<int> flow;

int cnt_k;

void check(int v, int prev, int d) {
        color[v] = d;
        if (d & 1) black_all ++;
        else white_all ++;
        for (auto u : g[v]) if (u != prev) { 
                if (color[u] == -1) {
                        check(u, v, 1 - d);
                } else {
                        start = v;
                        goal = u;
                        if (color[u] == 1 - d) { 
                                type = 1;
                        } else { 
                                type = 2;
                        }
                }
        }
}

pair<int, int> dfs(int v, int prev, int d) {
        int black = 0, white = 0;
        for (auto u : g[v]) if (u != prev) {
                pair<int, int> get = dfs(u, v, d + 1);
                black += get.first;
                white += get.second;
        }
        if (d & 1) black ++;
        else white ++;
        ans += abs(black - white);
        return make_pair(black, white);
}

pair<int, int> dfs2(int v, int prev, int d) {
        int black = 0, white = 0;
        in_start[v] = false, in_goal[v] = false;
        if (v == start) in_start[v] = true;
        if (v == goal) in_goal[v] = true;
        for (auto u : g[v]) if (u != prev) {
                pair<int, int> get = dfs2(u, v, d + 1);
                in_start[v] |= in_start[u];
                in_goal[v] |= in_goal[u];
                black += get.first;
                white += get.second;
        }
        if (d & 1) black ++;
        else white ++;
        if ((in_start[v] && in_goal[v]) || (!in_start[v] && !in_goal[v])) {
                ans += abs(black - white);
        } else {
                flow.push_back(black - white);
        }
        return make_pair(black, white);
}

pair<int, int> dfs3(int v, int prev, int d) {
        int black = 0, white = 0;
        for (auto u : g[v]) if (u != prev) {
                pair<int, int> get = dfs3(u, v, d + 1);
                black += get.first;
                white += get.second;
        }
        if (d & 1) black ++;
        else white ++;
        if (v == start || v == goal) black -= cnt_k;
        ans += abs(black - white);
        return make_pair(black, white);
}

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);
        }
        type = 0;
        memset(color, -1, sizeof color);
        check(0, -1, 0);
        if (type == 0 || type == 1) {
                if (black_all != white_all) {
                        puts("-1");
                        return 0;
                }
        }
        if (type == 2) {
                if (black_all % 2 != white_all % 2) {
                        puts("-1");
                        return 0;
                }
        }
        if (type == 0) {
                dfs(0, -1, 0);
                printf("%lld\n", ans);
                return 0;
        }
        for (int i = 0; i < g[start].size(); i ++) {
                if (g[start][i] == goal) {
                        g[start].erase(g[start].begin() + i);
                }
        }
        for (int i = 0; i < g[goal].size(); i ++) {
                if (g[goal][i] == start) {
                        g[goal].erase(g[goal].begin() + i);
                }
        }
        if (type == 1) {
                for (int i = 0; i < g[start].size(); i ++) {
                        if (g[start][i] == goal) {
                                g[start].erase(g[start].begin() + i);
                        }
                }
                for (int i = 0; i < g[goal].size(); i ++) {
                        if (g[goal][i] == start) {
                                g[goal].erase(g[goal].begin() + i);
                        }
                }
                dfs2(0, -1, 0);
                int lb = -101010, ub = 101010;
                int cnt = 0;
                while (ub - lb > 0) {
                        cnt ++;
                        if (cnt > 100) break;
                        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;
                }
                int res = 0x3f3f3f3f;
                for (int i = lb - 10; i < lb + 10; i ++) {
                        int 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;
        }
        if (type == 2) {
                cnt_k = (black_all - white_all) / 2;
                dfs3(0, -1, 0);
                ans += abs(cnt_k);
                printf("%lld\n", ans);
        }
        return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:86: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:89: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