Submission #3637455
Source Code Expand
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll mod = 1e9+7;
ll inf=1e18;
//WA
bool ok=true;
ll n,m,d[710][710],visit[710]={},color[710]={},dp[710]={},smallest=1e9;
vector<int> c1,c2;
int main(void){
rep(i,710)rep(j,710)d[i][j]=0;
cin>>n>>m;
rep(i,m){
ll a,b;
cin>>a>>b;
d[a-1][b-1]=1;
d[b-1][a-1]=1;
}
rep(i,n)rep(j,n){
if(i==j)continue;//補グラフでも自己辺は認めない
d[i][j]=1-d[i][j];
}
//孤立点があった時にどうするか
rep(i,n){
if(visit[i]==0){
int a[3]={};
a[1]++;
visit[i]=1;
color[i]=1;
queue<mp> Q;
Q.push({i,1});
while(!Q.empty()){
mp p=Q.front();Q.pop();
rep(j,n){
if(d[p.first][j]==1){
if(visit[j]==0){
visit[j]=1;
color[j]=3-p.second;
a[color[j]]++;
Q.push({j,color[j]});
}else{
if(color[j]!=3-color[p.first]){
ok=false;
break;
}
}
}
}
}
//孤立点でも1,0になるので行けるか?
c1.push_back(a[1]);
c2.push_back(a[2]);
}
}
// rep(i,c1.size())cout<<"c1:"<<c1[i]<<endl;
// rep(i,c2.size())cout<<"c2:"<<c2[i]<<endl;
//可能な数を列挙
dp[0]=1;
rep(i,c1.size()){
int dp2[710]={};
rep(j,710){
if(dp[j]==1){
if(j+c1[i]<710)dp2[j+c1[i]]=1;
if(j+c2[i]<710)dp2[j+c2[i]]=1;
}
}
rep(j,710)dp[j]=dp2[j];
}
rep(i,710){
if(dp[i]==1){
smallest=min(smallest,i*(i-1)/2+(n-i)*(n-i-1)/2);//ここを最小にする
}
}
cout<<(ok?smallest:-1)<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Independence |
User |
RMQ |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2039 Byte |
Status |
AC |
Exec Time |
108 ms |
Memory |
4224 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt |
Case Name |
Status |
Exec Time |
Memory |
1.txt |
AC |
4 ms |
4224 KB |
10.txt |
AC |
5 ms |
4224 KB |
11.txt |
AC |
100 ms |
4224 KB |
12.txt |
AC |
96 ms |
4224 KB |
13.txt |
AC |
89 ms |
4224 KB |
14.txt |
AC |
80 ms |
4224 KB |
15.txt |
AC |
104 ms |
4224 KB |
16.txt |
AC |
98 ms |
4224 KB |
17.txt |
AC |
100 ms |
4224 KB |
18.txt |
AC |
21 ms |
4224 KB |
19.txt |
AC |
108 ms |
4224 KB |
2.txt |
AC |
20 ms |
4224 KB |
20.txt |
AC |
104 ms |
4224 KB |
21.txt |
AC |
99 ms |
4224 KB |
22.txt |
AC |
101 ms |
4224 KB |
23.txt |
AC |
107 ms |
4224 KB |
24.txt |
AC |
69 ms |
4224 KB |
25.txt |
AC |
3 ms |
4224 KB |
26.txt |
AC |
3 ms |
4224 KB |
27.txt |
AC |
3 ms |
4224 KB |
28.txt |
AC |
3 ms |
4224 KB |
29.txt |
AC |
3 ms |
4224 KB |
3.txt |
AC |
104 ms |
4224 KB |
4.txt |
AC |
107 ms |
4224 KB |
5.txt |
AC |
101 ms |
4224 KB |
6.txt |
AC |
94 ms |
4224 KB |
7.txt |
AC |
105 ms |
4224 KB |
8.txt |
AC |
5 ms |
4224 KB |
9.txt |
AC |
20 ms |
4224 KB |
sample1.txt |
AC |
3 ms |
4224 KB |
sample2.txt |
AC |
3 ms |
4224 KB |
sample3.txt |
AC |
3 ms |
4224 KB |
sample4.txt |
AC |
3 ms |
4224 KB |