Submission #1641415
Source Code Expand
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100005,maxm=400005;
int last[maxn],pre[maxm],other[maxm],t,cal[maxn],vis[maxn],q[maxn],head,tail;
int n,m,x,y;
void add(int x,int y)
{
++t;
pre[t]=last[x];
last[x]=t;
other[t]=y;
}
inline int read(void)
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar(); }
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();}
return x*f;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
ll I=0,P=0,Q=0;
memset(last,0,sizeof(last));t=0;memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));memset(other,0,sizeof(other));
for(int i=1;i<=m;++i){
x=read(),y=read();add(x,y);add(y,x);
}
for(int i=1;i<=n;++i)if(!vis[i])
{
head=tail=0;
q[++tail]=i;
cal[i]=0;
vis[i]=1;
bool flag=1;
while(head<tail)
{
int u=q[++head];
for(int j=last[u];j;j=pre[j])
{
int v=other[j];
if(!vis[v])
{
q[++tail]=v;vis[v]=1;cal[v]=cal[u]+1;
}
else
{
if((cal[v]-cal[u])%2==0)flag=0;
}
}
}
if(head==1)
{++I;continue;}
if(flag)++Q;
else ++P;
}
printf("%lld\n",2ll*I*n-I*I+P*P+2ll*P*Q+2ll*Q*Q);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Squared Graph |
User |
vjudge4 |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1500 Byte |
Status |
AC |
Exec Time |
27 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 |
2 ms |
4096 KB |
in10.txt |
AC |
2 ms |
4480 KB |
in11.txt |
AC |
2 ms |
4096 KB |
in12.txt |
AC |
7 ms |
4480 KB |
in13.txt |
AC |
8 ms |
4480 KB |
in14.txt |
AC |
13 ms |
4480 KB |
in15.txt |
AC |
3 ms |
4480 KB |
in16.txt |
AC |
11 ms |
4480 KB |
in17.txt |
AC |
9 ms |
4480 KB |
in18.txt |
AC |
20 ms |
4608 KB |
in19.txt |
AC |
15 ms |
4736 KB |
in2.txt |
AC |
2 ms |
4096 KB |
in20.txt |
AC |
15 ms |
4736 KB |
in21.txt |
AC |
27 ms |
4864 KB |
in22.txt |
AC |
23 ms |
4096 KB |
in23.txt |
AC |
19 ms |
4096 KB |
in24.txt |
AC |
2 ms |
4480 KB |
in25.txt |
AC |
27 ms |
4864 KB |
in26.txt |
AC |
2 ms |
4096 KB |
in27.txt |
AC |
2 ms |
4096 KB |
in28.txt |
AC |
27 ms |
4864 KB |
in3.txt |
AC |
2 ms |
4096 KB |
in4.txt |
AC |
2 ms |
4096 KB |
in5.txt |
AC |
21 ms |
4480 KB |
in6.txt |
AC |
3 ms |
4480 KB |
in7.txt |
AC |
3 ms |
4480 KB |
in8.txt |
AC |
4 ms |
4480 KB |
in9.txt |
AC |
10 ms |
4480 KB |
sample1.txt |
AC |
2 ms |
4096 KB |
sample2.txt |
AC |
2 ms |
4096 KB |