Submission #935904

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int A, B, nr1, N, M, sub[100009][2], col[100009], ap[100009], sz[100009];
long long currCost, ans;
vector < int > v[100009];

void dfsTree (int nod, int tata)
{
    sub[nod][col[nod]] = 1;
    for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
        if (*it != tata)
            col[*it] = col[nod] ^ 1, dfsTree (*it, nod), sub[nod][0] += sub[*it][0], sub[nod][1] += sub[*it][1];
    int mod = sub[nod][0] - sub[nod][1];
    if (mod < 0) mod = -mod;
    ans += mod;
}

void dfs (int nod, int tata)
{
    ap[nod] = 1, sub[nod][0] = (col[nod] == 0), nr1 += (col[nod] == 1);
    for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
        if (ap[*it] == 0) col[*it] = col[nod] ^ 1, dfs (*it, nod), sub[nod][0] += sub[*it][0];
        else
        if (*it != tata) A = nod, B = *it;
}

void dfsEven (int nod, int tata)
{
    ap[nod] = 1;
    for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
        if (ap[*it] == 0) dfsEven (*it, nod), sz[nod] += sz[*it];
    int mod = sub[nod][0] - sz[nod];
    if (mod < 0) mod = -mod;
    currCost += mod;
}

void dfsOdd (int nod, int tata)
{
    ap[nod] = 1;
    for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
        if (ap[*it] == 0) dfsOdd (*it, nod), sz[nod] += sz[*it];
    int mod = sub[nod][0] - sz[nod];
    if (mod < 0) mod = -mod;
    ans += mod;
}

long long EvenF (int F)
{
    for (int i=1; i<=N; i++)
        sz[i] = col[i], ap[i] = 0;
    sz[A] += F, sz[B] -= F, currCost = F;
    if (F < 0) currCost = -F;
    dfsEven (1, -1);
//    printf ("%d -> %lld\n", F, currCost);
    if (currCost < ans) ans = currCost;
    return currCost;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d\n", &N, &M);
for (int i=1; i<=M; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    v[x].push_back (y);
    v[y].push_back (x);
}
if (M == N - 1)
{
    dfsTree (1, -1);
    if (sub[1][0] != sub[1][1]) printf ("-1\n");
    else printf ("%lld\n", ans);
    return 0;
}
dfs (1, -1);
if (col[A] != col[B])
{
    ///Even cycle
    if (sub[1][0] != nr1)
    {
        printf ("-1\n");
        return 0;
    }
    ///let F pe the flow on edge B->A with -nr1 <= F <= nr1, we can just use the same algo as for tree,
    ///increasing the number of tokens in A by F and decreasing it in B
    ///thie way, we'll get a sum of expressions of the form |F - constant| + some constant that we need to minimize
    ///there are multiple ways of doing it(F is the median of the constants for example), but the easiest to implement
    ///is ternary search
    int st = -nr1, dr = nr1;
    ans = 1LL << 50;
    while (1)
    {
        if (dr - st <= 2)
        {
            for (int i=st; i<=dr; i++)
                EvenF (i);
            break;
        }
        int mid1 = st + (dr - st) / 3, mid2 = dr - (dr - st) / 3;
        long long C1 = EvenF (mid1), C2 = EvenF (mid2);
        if (C1 < C2) dr = mid2;
        else st = mid1;
    }
    printf ("%lld\n", ans);
    return 0;
}
///Odd cycle
if (sub[1][0] % 2 != nr1 % 2)
{
    printf ("-1\n");
    return 0;
}
int K = (sub[1][0] - nr1) / 2;
for (int i=1; i<=N; i++)
    sz[i] = col[i], ap[i] = 0;
sz[A] += K, sz[B] += K, ans = K;
if (ans < 0) ans = -ans;
dfsOdd (1, -1);
printf ("%lld\n", ans);
return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d\n", &N, &M);
                          ^
./Main.cpp:70:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x, &y);
                            ^

Judge Result