Submission #5906639

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
const int MAX=710;
const int INF=1e9+50;

bool ed[MAX][MAX];
int N, M;
int vx[MAX];
vi c1, c2;

bool dfs(int s, int c){
	vx[s]=c;
	rep(i,N)if(i!=s && !ed[s][i]){
		if(vx[i]==c) return false;
		if(vx[i]==0 && !dfs(i, -c)) return false;
	}
	return true;
}

bool dp[MAX][MAX];

int main(){
	cin>>N>>M;
	rep(_,M){
		int a, b;
		cin>>a>>b;
		a--;
		b--;
		ed[a][b]=true;
		ed[b][a]=true;
	}
	int ans=0;
	int co=1;
	rep(i,N){
		if(vx[i]==0){
			bool f=dfs(i, co);
			if(f) co++;
			else{
				ans=-1;
				break;
			}
		}
	}
	if(ans==-1){
		cout<<-1<<endl;
		return 0;
	}
	int ct1[MAX] ,ct2[MAX];
	rep1(i,co-1){
		ct1[i]=0;
		ct2[i]=0;
	}
	rep(i,N){
		int c=vx[i];
		if(c>0)ct1[c]++;
		if(c<0)ct2[-c]++;
	}
	dp[0][0]=true;
	rep1(i,co-1)rep(j,N+1){
		if(j-ct1[i]>=0 && dp[i-1][j-ct1[i]])dp[i][j]=true;
		if(j-ct2[i]>=0 && dp[i-1][j-ct2[i]])dp[i][j]=true;
	}
  	int tak;
	for(int j=N/2; j>=0; j--)if(dp[co-1][j]){
    	tak=j;
        break;
    }
  	int aok=N-tak;
  	ans=(tak*(tak-1))/2+(aok*(aok-1))/2;
  	cout<<ans<<endl;
}

Submission Info

Judge Result