Submission #1869534
Source Code Expand
#include<cstdio> using namespace std; typedef long long ll; const int N=100100,M=400400; int i,j,k,n,m,ch,ff,x,y,fg,n1,n2,n3,En; ll ans; int h[N],z[N]; struct edge { int s,n;} E[M]; void R(int &x) { x=0;ch=getchar(); while (ch<'0' || '9'<ch) { if (ch=='-') ff=1;ch=getchar();} while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar(); if (ff) x=-x; } void W(ll x) { if (x<0) putchar('-'),x=-x; if (x>=10) W(x/10); putchar(x%10+'0'); } void E_add(int x,int y) { E[++En].s=y;E[En].n=h[x];h[x]=En; E[++En].s=x;E[En].n=h[y];h[y]=En; } void dfs(int x,int y) { z[x]=y; for (int k=h[x];k;k=E[k].n) { if (!z[E[k].s]) dfs(E[k].s,3-y); else { if (z[E[k].s]!=3-y) fg=0; } } } int main() { R(n);R(m); for (i=1;i<=m;i++) { R(x);R(y); E_add(x,y); } for (i=1;i<=n;i++) if (!z[i]) { if (!h[i]) n1++; else { fg=1; dfs(i,1); n2+=fg; n3+=fg^1; } } ans=(ll) n1*(2*n-n1)+2ll*n2*n2+(ll) n3*n3+2ll*n2*n3; W(ans);puts(""); }
Submission Info
Submission Time | |
---|---|
Task | C - Squared Graph |
User | jiyutian |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 996 Byte |
Status | AC |
Exec Time | 33 ms |
Memory | 5888 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 | 128 KB |
in10.txt | AC | 1 ms | 128 KB |
in11.txt | AC | 1 ms | 128 KB |
in12.txt | AC | 7 ms | 1664 KB |
in13.txt | AC | 7 ms | 1664 KB |
in14.txt | AC | 14 ms | 2560 KB |
in15.txt | AC | 2 ms | 1024 KB |
in16.txt | AC | 11 ms | 2048 KB |
in17.txt | AC | 9 ms | 2048 KB |
in18.txt | AC | 22 ms | 3712 KB |
in19.txt | AC | 17 ms | 3456 KB |
in2.txt | AC | 1 ms | 128 KB |
in20.txt | AC | 17 ms | 3328 KB |
in21.txt | AC | 33 ms | 5888 KB |
in22.txt | AC | 26 ms | 3712 KB |
in23.txt | AC | 23 ms | 3328 KB |
in24.txt | AC | 1 ms | 896 KB |
in25.txt | AC | 33 ms | 5888 KB |
in26.txt | AC | 1 ms | 128 KB |
in27.txt | AC | 1 ms | 256 KB |
in28.txt | AC | 33 ms | 5888 KB |
in3.txt | AC | 1 ms | 128 KB |
in4.txt | AC | 1 ms | 128 KB |
in5.txt | AC | 25 ms | 3584 KB |
in6.txt | AC | 2 ms | 1024 KB |
in7.txt | AC | 2 ms | 1024 KB |
in8.txt | AC | 3 ms | 1152 KB |
in9.txt | AC | 10 ms | 2304 KB |
sample1.txt | AC | 1 ms | 128 KB |
sample2.txt | AC | 1 ms | 128 KB |