Submission #1348874

---

Source Code Expand

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

const int DIM = 1e5 + 5;

int cnt[DIM], lev[DIM], fth[DIM];
vector<int> edg[DIM]; pair<int, int> lst[DIM];

void dfs( int x, int f, int &cnt1, int &cnt2, int &p, int &q ) {
    lev[x] = lev[f] + 1; fth[x] = f;
    
    if( cnt[x] == 1 ) cnt1 ++;
    else              cnt2 ++;
    
    int val = -cnt[x];
    for( int y : edg[x] ) {
        if( y == f )
            continue;
        
        if( lev[y] == 0 ) {
            cnt[y] = val;
            dfs( y, x, cnt1, cnt2, p, q );
            cnt[x] += cnt[y];
        }
        else
        if( lev[x] > lev[y] )
            p = x, q = y;
    }
    
    return;
}

int solve( int m, int p, int q ) {
    int ans = 0;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y;
        tie( x, y ) = lst[i];
        
        if( x == p && y == q ) continue;
        if( y == p && x == q ) continue;
        
        if( lev[x] > lev[y] )
            swap( x, y );
        ans += abs( cnt[y] );
    }
    
    return ans;
}

int main( void ) {
    
    int n, m;
    cin >> n >> m;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y;
        cin >> x >> y;
        
        edg[x].push_back( y );
        edg[y].push_back( x );
        lst[i] = make_pair( x, y );
    }
    
    int cnt1 = 0, cnt2 = 0, p, q;
    cnt[1] = 1; dfs( 1, 0, cnt1, cnt2, p, q );
    
    if( n == m + 1 ) { // tree
        if( cnt1 != cnt2 )
            cout << -1 << endl;
        else
            cout << solve( m, 0, 0 ) << endl;
    }
    else
    if( ( lev[p] - lev[q] ) & 1 ) { // even cycle
        if( cnt1 != cnt2 )
            cout << -1 << endl;
        else {
            vector<int> aux;
            for( int i = p; i != q; i = fth[i] )
                aux.push_back( cnt[i] );
            
            sort( aux.begin(), aux.end() );
            int ans = aux[(aux.size() + 1) / 2 - 1];
            
            for( int i = p; i != q; i = fth[i] )
                cnt[i] -= ans;
            
            ans = abs( ans );
            ans += solve( m, p, q );
            
            cout << ans << endl;
        }
    }
    else { // odd cycle
        if( abs( cnt2 - cnt1 ) & 1 )
            cout << -1 << endl;
        else {
            int ans = ( cnt2 - cnt1 ) / 2;
            
            for( int i = p; i != 0; i = fth[i] )
                cnt[i] += ans;
            for( int i = q; i != 0; i = fth[i] )
                cnt[i] += ans;
            
            ans = abs( ans );
            ans += solve( m, p, q );
            
            cout << ans << endl;
        }
    }
    
    return 0;
}

Submission Info

Judge Result