Submission #3880132

---

Source Code Expand

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef unsigned int uint;
typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

const int MX = 200005;

struct UF{
	int t[MX], c1[MX], c2[MX];
	int find(int x){ return t[x] ? t[x] = find(t[x]) : x; }
	int merge(int a, int b){ // a <- b
		a = find(a), b = find(b);
		if(a == b) return false;
		t[b] = a; c1[a] += c1[b]; c2[a] += c2[b];
		return true;
	}
}uf;

int dp[MX], tdp[MX];

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	set<pii> L;
	for(int i = 1; i <= N; i++){
		for(int j = i+1; j <= N; j++) L.emplace(i, j);
	}
	for(int i = 1; i <= M; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		if(a > b) swap(a, b);
		L.erase(pii(a, b));
	}
	for(int i = 1; i <= N; i++) uf.c1[i*2] = uf.c2[i*2+1] = 1;
	for(pii c : L){
		uf.merge(c.second*2, c.first*2+1);
		uf.merge(c.first*2, c.second*2+1);
	}

	for(int i = 1; i <= N; i++) if(uf.find(i*2) == uf.find(i*2+1)) return !printf("-1\n");
	for(int i = 1; i <= N; i++){
		if(uf.find(i*2) != uf.find(i*2+1)) uf.t[uf.find(i*2)] = uf.find(i*2+1);
	}

	dp[0] = 1;
	for(int i = 2; i <= 2*N+1; i ++){
		if(uf.find(i) != i) continue;
		for(int i = 0; i <= N; i++) tdp[i] = 0;
		
		int c = uf.c1[i];
		for(int t = N; t >= c; t--) tdp[t] |= dp[t-c];
		
		c = uf.c2[i];
		for(int t = N; t >= c; t--) tdp[t] |= dp[t-c];
		
		for(int i = 0; i <= N; i++) dp[i] = tdp[i];
	}
	int ans = 1e9;
	for(int i = 1; i < N; i++) if(dp[i]) ans = min(ans, i*(i-1)/2 + (N-i)*(N-i-1)/2);
	if(ans == 1e9) ans = -1;
	printf("%d\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:79:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^

Judge Result