Submission #1691136


Source Code Expand

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

#define int long long

vector<signed> g[101010];
signed color[101010];
long long black, white, type, cnt;
signed s, t;
long long ans;

bool in_s[101010], in_t[101010];
vector<long long> flow;

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

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

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

signed main() {
        long long n, m;
        scanf("%lld%lld", &n, &m);
        for (int i = 0; i < m; i ++) {
                long long 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 && black != white) ||
            (type == 1 && black != white) ||
            (type == 2 && black % 2 != white % 2)) {
                puts("-1");
                return 0;
        }
        if (type == 0) dfs(0, -1, 0);
        g[s].erase(remove(g[s].begin(), g[s].end(), t), g[s].end());
        g[t].erase(remove(g[t].begin(), g[t].end(), s), g[t].end());
        if (type == 1) {
                dfs2(0, -1, 0);
                long long lb = -101010, ub = 101010;
                while (ub - lb > 3) {
                        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 (long long 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;
        }
        if (type == 2) {
                cnt = (black - white) / 2;
                dfs(0, -1, 0);
                ans += abs(cnt);
        }
        printf("%lld\n", ans);
        return 0;
}

Submission Info

Submission Time
Task F - Namori
User KokiYmgch
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 4001 Byte
Status AC
Exec Time 61 ms
Memory 18424 KB

Compile Error

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

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 1500 / 1500 700 / 700
Status
AC × 4
AC × 20
AC × 66
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 3 ms 2944 KB
0_01.txt AC 3 ms 2944 KB
0_02.txt AC 3 ms 3072 KB
0_03.txt AC 3 ms 3072 KB
1_00.txt AC 3 ms 3072 KB
1_01.txt AC 50 ms 13696 KB
1_02.txt AC 40 ms 8448 KB
1_03.txt AC 30 ms 6520 KB
1_04.txt AC 45 ms 9728 KB
1_05.txt AC 47 ms 9344 KB
1_06.txt AC 47 ms 9344 KB
1_07.txt AC 44 ms 8576 KB
1_08.txt AC 47 ms 9984 KB
1_09.txt AC 39 ms 6528 KB
1_10.txt AC 40 ms 6272 KB
1_11.txt AC 42 ms 6272 KB
1_12.txt AC 44 ms 6144 KB
1_13.txt AC 40 ms 6528 KB
1_14.txt AC 39 ms 6272 KB
1_15.txt AC 44 ms 6144 KB
1_16.txt AC 40 ms 6144 KB
1_17.txt AC 44 ms 6144 KB
2_00.txt AC 3 ms 3072 KB
2_01.txt AC 60 ms 18424 KB
2_02.txt AC 46 ms 12672 KB
2_03.txt AC 30 ms 6776 KB
2_04.txt AC 50 ms 12540 KB
2_05.txt AC 52 ms 12544 KB
2_06.txt AC 52 ms 12412 KB
2_07.txt AC 51 ms 12540 KB
2_08.txt AC 52 ms 12412 KB
2_09.txt AC 40 ms 6656 KB
2_10.txt AC 43 ms 6528 KB
2_11.txt AC 43 ms 6400 KB
2_12.txt AC 45 ms 6400 KB
2_13.txt AC 41 ms 8192 KB
2_14.txt AC 39 ms 6400 KB
2_15.txt AC 45 ms 6400 KB
2_16.txt AC 40 ms 6144 KB
2_17.txt AC 45 ms 6400 KB
2_18.txt AC 3 ms 3072 KB
2_19.txt AC 41 ms 10236 KB
2_20.txt AC 31 ms 6520 KB
2_21.txt AC 61 ms 18424 KB
2_22.txt AC 45 ms 10240 KB
2_23.txt AC 46 ms 10240 KB
2_24.txt AC 47 ms 10112 KB
2_25.txt AC 44 ms 10368 KB
2_26.txt AC 47 ms 10112 KB
2_27.txt AC 39 ms 6528 KB
2_28.txt AC 41 ms 6272 KB
2_29.txt AC 42 ms 6272 KB
2_30.txt AC 44 ms 6144 KB
2_31.txt AC 41 ms 7680 KB
2_32.txt AC 44 ms 6400 KB
2_33.txt AC 44 ms 6272 KB
2_34.txt AC 39 ms 6144 KB
2_35.txt AC 47 ms 6144 KB
2_36.txt AC 30 ms 6776 KB
2_37.txt AC 30 ms 6776 KB
2_38.txt AC 30 ms 6776 KB
2_39.txt AC 30 ms 6776 KB
2_40.txt AC 30 ms 6776 KB
2_41.txt AC 30 ms 6776 KB
2_42.txt AC 30 ms 6776 KB
2_43.txt AC 29 ms 6776 KB