Submission #870289


Source Code Expand

#include<assert.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

int N, M;

VI G[100111];
int deg[100111];
int C_sum;
int C[100111];
bool use[100111];
int A[100111], B[100111];
LL dp[100111];

VI ord;
void color() {
    ord.reserve(N);
    ord.push_back(0);
    C_sum = 1;
    C[0] = 1;

    REP (_, N) {
	int v = ord[_];

	EACH (e, G[v]) {
	    G[*e].erase(remove(G[*e].begin(), G[*e].end(), v), G[*e].end());

	    if (C[v] == 1) {
		C_sum--;
		C[*e] = -1;
	    } else {
		C_sum++;
		C[*e] = 1;
	    }

	    ord.push_back(*e);
	}
    }
}
LL solve() {
    LL ret = 0;
    REP (_, N) {
	int v = ord[N-1-_];
	dp[v] = C[v];
	EACH (e, G[v]) {
	    dp[v] += dp[*e];
	}

	ret += abs(C_sum - 2 * dp[v]);
    }

    assert(ret % 2 == 0);
    return ret / 2;
}

int main() {
    scanf("%d%d", &N, &M);
    REP (i, M) {
	scanf("%d%d", A+i, B+i);
	A[i]--;
	B[i]--;
	G[A[i]].push_back(B[i]);
	G[B[i]].push_back(A[i]);
    }

    LL ans = 0;

    if (M == N - 1) {
	color();
	if (C_sum) {
	    ans = -1;
	} else {
	    ans = solve();
	}
    } else {

	stack<int> S;
	REP (i, N) {
	    deg[i] = G[i].size();
	    if (deg[i] == 1) S.push(i);
	}

	while (!S.empty()) {
	    int v = S.top(); S.pop();

	    use[v] = true;

	    EACH (e, G[v]) {
		deg[*e]--;
		if (deg[*e] == 1) S.push(*e);
	    }
	}


	int root = 0;
	REP (i, N) if (!use[i]) {
	    root = i;
	    break;
	}

	int cur = root;
	VI X;
	while (true) {
//	    eprintf("%d %d", cur, C[cur]); eprintf("\n");
	    X.push_back(cur);
	    use[cur] = true;

	    bool update = false;
	    EACH (e, G[cur]) if (!use[*e]) {
		cur = *e;
		update = true;
		break;
	    }

	    if (!update) break;
	}

	int x0 = X[0], x1 = X[1];
	G[x0].erase(remove(G[x0].begin(), G[x0].end(), x1), G[x0].end());
	G[x1].erase(remove(G[x1].begin(), G[x1].end(), x0), G[x1].end());


	color();

	if (X.size() & 1) {
	    if (C_sum & 1) {
		ans = -1;
	    } else {
		C[x0] -= C_sum / 2;
		C[x1] -= C_sum / 2;
		ans = abs(C_sum) / 2;
		C_sum = 0;
		ans += solve();
	    }
	} else {

	    if (C_sum != 0) {
		ans = -1;
	    } else {
		int lo = -N, hi = N;

		while (hi - lo > 2) {
		    int llh = (lo + lo + hi) / 3;
		    int lhh = (lo + hi + hi) / 3;
		    C[x0] -= llh;
		    C[x1] += llh;
		    LL tmp_0 = solve() + abs(llh);
		    C[x0] += llh;
		    C[x1] -= llh;

		    C[x0] -= lhh;
		    C[x1] += lhh;
		    LL tmp_1 = solve() + abs(lhh);
		    C[x0] += lhh;
		    C[x1] -= lhh;


		    if (tmp_0 < tmp_1) hi = lhh;
		    else lo = llh;
		}

		ans = 1LL<<60;
		for (int i=lo; i<=hi; i++) {
		    C[x0] -= i;
		    C[x1] += i;
		    LL tmp = solve() + abs(i);
		    C[x0] += i;
		    C[x1] -= i;
		    amin(ans, tmp);
		}
	    }
	}
    }

    printf("%lld\n", ans);


    return 0;
}

Submission Info

Submission Time
Task F - Namori
User natsugiri
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 3388 Byte
Status AC
Exec Time 315 ms
Memory 9336 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73: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:75:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", A+i, B+i);
                         ^

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 7 ms 2560 KB
0_01.txt AC 8 ms 2560 KB
0_02.txt AC 8 ms 2560 KB
0_03.txt AC 7 ms 2560 KB
1_00.txt AC 8 ms 2560 KB
1_01.txt AC 83 ms 8064 KB
1_02.txt AC 73 ms 8320 KB
1_03.txt AC 65 ms 8440 KB
1_04.txt AC 81 ms 8192 KB
1_05.txt AC 85 ms 8064 KB
1_06.txt AC 83 ms 8064 KB
1_07.txt AC 83 ms 8192 KB
1_08.txt AC 83 ms 8192 KB
1_09.txt AC 77 ms 8448 KB
1_10.txt AC 81 ms 8192 KB
1_11.txt AC 84 ms 8192 KB
1_12.txt AC 85 ms 8064 KB
1_13.txt AC 78 ms 7296 KB
1_14.txt AC 79 ms 7296 KB
1_15.txt AC 86 ms 8064 KB
1_16.txt AC 81 ms 7296 KB
1_17.txt AC 85 ms 8064 KB
2_00.txt AC 8 ms 2560 KB
2_01.txt AC 278 ms 9080 KB
2_02.txt AC 230 ms 9084 KB
2_03.txt AC 173 ms 9336 KB
2_04.txt AC 308 ms 9084 KB
2_05.txt AC 289 ms 8956 KB
2_06.txt AC 302 ms 9024 KB
2_07.txt AC 271 ms 9084 KB
2_08.txt AC 299 ms 8956 KB
2_09.txt AC 229 ms 9216 KB
2_10.txt AC 259 ms 8960 KB
2_11.txt AC 301 ms 8832 KB
2_12.txt AC 312 ms 8704 KB
2_13.txt AC 89 ms 8256 KB
2_14.txt AC 89 ms 7936 KB
2_15.txt AC 315 ms 8704 KB
2_16.txt AC 91 ms 7936 KB
2_17.txt AC 301 ms 8704 KB
2_18.txt AC 8 ms 2560 KB
2_19.txt AC 84 ms 9148 KB
2_20.txt AC 72 ms 9336 KB
2_21.txt AC 269 ms 9080 KB
2_22.txt AC 90 ms 9084 KB
2_23.txt AC 96 ms 9084 KB
2_24.txt AC 95 ms 9024 KB
2_25.txt AC 89 ms 9212 KB
2_26.txt AC 94 ms 8956 KB
2_27.txt AC 86 ms 9216 KB
2_28.txt AC 91 ms 8960 KB
2_29.txt AC 95 ms 8960 KB
2_30.txt AC 96 ms 8704 KB
2_31.txt AC 89 ms 8060 KB
2_32.txt AC 93 ms 8704 KB
2_33.txt AC 97 ms 8704 KB
2_34.txt AC 90 ms 7936 KB
2_35.txt AC 95 ms 8704 KB
2_36.txt AC 170 ms 9336 KB
2_37.txt AC 169 ms 9336 KB
2_38.txt AC 165 ms 9336 KB
2_39.txt AC 175 ms 9336 KB
2_40.txt AC 165 ms 9336 KB
2_41.txt AC 170 ms 9336 KB
2_42.txt AC 169 ms 9336 KB
2_43.txt AC 170 ms 9336 KB