Submission #1592018
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,m,tot,b[100001],s,a,bi; char vis[100001],col[100001]; struct Edge{ int to,nxt; }e[400001]; void dfs1(int x){ vis[x]=1; for (int i=b[x];i;i=e[i].nxt){ int p=e[i].to; if (!vis[p]) dfs1(p); } } int dfs(int x,char c){ vis[x]=1; col[x]=c; c^=1; int ans=1; //printf("x=%d\n"); for (int i=b[x];i;i=e[i].nxt){ int p=e[i].to; if (!ans) dfs1(p); else if (col[p]!=-1){ if (col[p]!=c) ans=0; }else ans=dfs(p,c); } return ans; } void read(int& x){ x=0; int y=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') y=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x=x*y; } int main(){ int i,x,y,t=0,j,k,l; long long ans; read(n); read(m); for (i=1;i<=m;++i){ read(x); read(y); e[++tot]=(Edge){y,b[x]}; b[x]=tot; e[++tot]=(Edge){x,b[y]}; b[y]=tot; } for (i=1;i<=n;++i) if (!b[i]){ ++s; vis[i]=1; } memset(col,-1,sizeof(col)); for (i=1;i<=n;++i){ if (!vis[i]){ //printf("ok"); if (!dfs(i,0)) ++bi;//非二分 else ++a;//二分 } } ans=(long long)s*((n<<1)-s)+(long long)a*a+(long long)(a+bi)*(a+bi); printf("%lld\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Squared Graph |
User | vjudge4 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1295 Byte |
Status | AC |
Exec Time | 437 ms |
Memory | 4864 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt |
All | sample1.txt, sample2.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 1 ms | 384 KB |
in10.txt | AC | 1 ms | 512 KB |
in11.txt | AC | 1 ms | 384 KB |
in12.txt | AC | 8 ms | 1664 KB |
in13.txt | AC | 8 ms | 1664 KB |
in14.txt | AC | 14 ms | 2432 KB |
in15.txt | AC | 3 ms | 896 KB |
in16.txt | AC | 12 ms | 2048 KB |
in17.txt | AC | 10 ms | 1792 KB |
in18.txt | AC | 21 ms | 3328 KB |
in19.txt | AC | 16 ms | 2816 KB |
in2.txt | AC | 1 ms | 384 KB |
in20.txt | AC | 16 ms | 2816 KB |
in21.txt | AC | 30 ms | 4864 KB |
in22.txt | AC | 32 ms | 3712 KB |
in23.txt | AC | 437 ms | 3456 KB |
in24.txt | AC | 2 ms | 896 KB |
in25.txt | AC | 31 ms | 4864 KB |
in26.txt | AC | 1 ms | 384 KB |
in27.txt | AC | 1 ms | 384 KB |
in28.txt | AC | 30 ms | 4864 KB |
in3.txt | AC | 1 ms | 384 KB |
in4.txt | AC | 1 ms | 384 KB |
in5.txt | AC | 41 ms | 3456 KB |
in6.txt | AC | 2 ms | 896 KB |
in7.txt | AC | 2 ms | 896 KB |
in8.txt | AC | 4 ms | 1024 KB |
in9.txt | AC | 10 ms | 1920 KB |
sample1.txt | AC | 1 ms | 384 KB |
sample2.txt | AC | 1 ms | 384 KB |