Submission #868498

---

Source Code Expand

/**
 *    author:  [itmo] enot.1.10
 *    created: 04.09.2016 15:53:18       
**/
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define mp make_pair
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define pw(x) (1LL<<(x))

using namespace std;

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = 1.01e9;
const dbl eps = 1e-9;

/* --- main part --- */

int n, m;

namespace task1
{

const int N = 1e5 + 10;

int mark[N];
vi v[N];
int d[N][2];
ll res = 0;

void dfs(int x)
{
    mark[x] = 1;
    d[x][0] = 1;
    d[x][1] = 0;
    for (int y : v[x])
    {
        if (mark[y] == 1) continue;
        dfs(y);
        d[x][0] += d[y][1];
        d[x][1] += d[y][0];
    }
    res += abs(d[x][0] - d[x][1]);
}

void run()
{
    forn(i, n - 1)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        --x, --y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(0);
    if (d[0][0] != d[0][1]) res = -1;
    printf("%lld\n", res);
    exit(0);
}    

}

const int N = 1e5 + 10;

vi v[N];
vi cycle;
int cyc[N];
int mark[N];
int st[N], stc = 0;
int found = 0;

void dfs(int x, int pr = -1)
{
    mark[x] = 1;
    st[stc++] = x;
    for (int y : v[x])
    {
        if (y == pr) continue;
        if (mark[y] == 1)
        {
            if (found) continue;
            found = 1;
            for (int i = stc - 1; i >= 0; --i)
            {
                int z = st[i];
                cycle.pb(z);
                cyc[z] = 1;
                if (z == y) break;
            }
        }
        else
        {
            dfs(y, x);
        }
    }
    stc--;
}

ll res = 0;        
int d[N][2];

void calc(int x)
{
    mark[x] = 1;
    d[x][0] = 1;
    d[x][1] = 0;
    for (int y : v[x])
    {
        if (!cyc[y] && mark[y] == 0)
        {
            calc(y);
            d[x][0] += d[y][1];
            d[x][1] += d[y][0];
        }
    }
    if (!cyc[x]) res += abs(d[x][0] - d[x][1]);
}
            
int cnt[N];

ll f(int x, vi &v1, vi &v2)
{
    ll r = 0;
    forn(i, sz(v1)) r += abs(v1[i] - x);
    forn(i, sz(v2)) r += abs(v2[i] + x);
    return r;
}


int main()
{
    #ifdef home
        assert(freopen("1.in", "r", stdin));
        assert(freopen("1.out", "w", stdout));
    #endif
    scanf("%d%d", &n, &m);
    if (n == m + 1)
    {
        task1::run();
        return 0;
    }
    forn(i, m)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        --x, --y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(0);
    memset(mark, 0, sizeof mark);
    ll val = 0;
    forn(i, n) if (cyc[i])
    {
        calc(i);
        val += abs(d[i][0] - d[i][1]);
    }

    int cc = sz(cycle);
    /*forn(i, sz(cycle))
    {
        eprintf("%d%c", cycle[i], " \n"[i + 1 == sz(cycle)]);
    }  */
    forn(i, cc)
    {
        cnt[i] = d[cycle[i]][0] - d[cycle[i]][1];
    }        

    int ok = val % 2 == 0;
    if (!ok) return 0 * printf("-1\n");

    int a = 1, b = 0;
    for (int i = 1; i < cc; ++i)
    {
        int a2 = -a;
        int b2 = cnt[i] - b;
        a = a2, b = b2;
    }

    if (a == 1)
    {
        assert((cnt[0] - b) % 2 == 0);
        int x = (cnt[0] - b) / 2;
        res += abs(x);
        for (int i = 1; i < cc; ++i)
        {
            x = cnt[i] - x;
            res += abs(x);
        }
        printf("%lld\n", res);
    }
    else
    {
        if (b != cnt[0]) return 0 * printf("-1\n");
        vi v1, v2;
        int x = 0;
        v1.pb(x);
        for (int i = 1; i < cc; ++i)
        {
            x = cnt[i] - x;
            if (i % 2 == 0) v1.pb(x);
            else v2.pb(x);
        }
        int L = -1e8;
        int R = 1e8;
        while (R - L > 10)
        {
            int m1 = (2 * L + R) / 3;
            int m2 = (L + 2 * R) / 3;
            ll f1 = f(m1, v1, v2);
            ll f2 = f(m2, v1, v2);
            if (f1 < f2) R = m2;
            else L = m1;
        }
        ll ans = 1e18;
        for (int i = L; i <= R; ++i) ans = min(ans, f(i, v1, v2));
        res += ans;
        printf("%lld\n", res);
    }
    #ifdef home
        eprintf("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void task1::run()’:
./Main.cpp:62:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
                              ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:148: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:157: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