Submission #3242550
Source Code Expand
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<queue> #include<cmath> #include<cstdlib> #define LL long long #define LD long double using namespace std; const int NN=700 +117; const int MM=250000 +117; int read(){ int fl=1,x;char c; for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar()); if(c=='-'){fl=-1;c=getchar();} for(x=0;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x*fl; } void open(){ freopen("99e.in","r",stdin); //freopen("99e.cpp.out","w",stdout); } void close(){ fclose(stdin); fclose(stdout); } int m,n; int sq[NN][NN]={}; vector<int> p[NN]; vector<int> v; int has[2][NN]={}; int col[NN]={}; int dfs(int x,int c){ int res=c; col[x]=c; for(int i=0;i<p[x].size();++i){ int cur=p[x][i]; if(col[cur]==c){ return -2*n; } if(!col[cur]){ int tp=dfs(cur,-c); if(tp<-n)return -2*n; res+=tp; } } return res; } int main(){ open(); n=read(); m=read(); for(int i=1;i<=m;++i){ int x=read(),y=read(); sq[x][y]=1; sq[y][x]=1; } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(!sq[i][j]&&i!=j){ p[i].push_back(j); } } } for(int i=1;i<=n;++i){ if(!col[i]){ int tp=dfs(i,1); if(tp<-n){ printf("-1\n"); return 0; } v.push_back(abs(tp)); } } has[0][0]=1; int now=0; for(int pos=0;pos<v.size();++pos){ now^=1; for(int i=n;i>=0;--i){ if(has[now^1][i]){ has[now][abs(i-v[pos])]=1; has[now][i+v[pos]]=1; has[now^1][i]=0; } } } int ans=n; for(int i=0;i<=n;++i){ if(has[now][i])ans=min(ans,i); } int aa=(ans+n)/2; printf("%d\n",aa*(aa-1)/2+(n-aa)*(n-aa-1)/2); close(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Independence |
User | Hercier |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1760 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 256 KB |
Compile Error
./Main.cpp: In function ‘void open()’: ./Main.cpp:23:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result] freopen("99e.in","r",stdin); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | TLE | 2103 ms | 256 KB |
10.txt | TLE | 2103 ms | 256 KB |
11.txt | TLE | 2103 ms | 256 KB |
12.txt | TLE | 2103 ms | 256 KB |
13.txt | TLE | 2103 ms | 256 KB |
14.txt | TLE | 2103 ms | 256 KB |
15.txt | TLE | 2103 ms | 256 KB |
16.txt | TLE | 2103 ms | 256 KB |
17.txt | TLE | 2103 ms | 256 KB |
18.txt | TLE | 2103 ms | 256 KB |
19.txt | TLE | 2103 ms | 256 KB |
2.txt | TLE | 2103 ms | 256 KB |
20.txt | TLE | 2103 ms | 256 KB |
21.txt | TLE | 2103 ms | 256 KB |
22.txt | TLE | 2103 ms | 256 KB |
23.txt | TLE | 2103 ms | 256 KB |
24.txt | TLE | 2103 ms | 256 KB |
25.txt | TLE | 2103 ms | 256 KB |
26.txt | TLE | 2103 ms | 256 KB |
27.txt | TLE | 2103 ms | 256 KB |
28.txt | TLE | 2103 ms | 256 KB |
29.txt | TLE | 2103 ms | 256 KB |
3.txt | TLE | 2103 ms | 256 KB |
4.txt | TLE | 2103 ms | 256 KB |
5.txt | TLE | 2103 ms | 256 KB |
6.txt | TLE | 2103 ms | 256 KB |
7.txt | TLE | 2103 ms | 256 KB |
8.txt | TLE | 2103 ms | 256 KB |
9.txt | TLE | 2103 ms | 256 KB |
sample1.txt | TLE | 2103 ms | 256 KB |
sample2.txt | TLE | 2103 ms | 256 KB |
sample3.txt | TLE | 2103 ms | 256 KB |
sample4.txt | TLE | 2103 ms | 256 KB |