Submission #1574303
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define MAXM 400000
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
return sgn-'-'?ans:-ans;
}
int first[MAXN+5], con[MAXN+5], book[MAXN+5], sz[MAXN+5], N, M, I, B, G, tot; bool unbi[MAXN+5];
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex):to(_to),nex(_nex){}}e[MAXM+5];
inline void Add(int a, int b){e[tot] = Edge(b,first[a]), first[a] = tot++, e[tot] = Edge(a,first[b]), first[b] = tot++;}
void DFS(int p, int w){book[p] = w, ++sz[G]; for(rint u = first[p], v; ~u; u = e[u].nex) if(!book[v=e[u].to]) DFS(v,w^1); else if(book[v] == w) B -= !unbi[G], unbi[G] = true;}
int main()
{
N = read(), M = read(), memset(first+1,-1,N<<2); for(rint i = 1; i <= M; Add(read(),read()), i++);
for(rint i = 1; i <= N; book[i] ?: (DFS(con[++G]=i,2),I+=sz[G]==1), i++); B = G-I+B, G = G-I-B;
printf("%lld\n",2ll*I*N-1ll*I*I+1ll*G*G+2ll*G*B+2ll*B*B); return 0;
}
Submission Info
Submission Time |
|
Task |
C - Squared Graph |
User |
vjudge4 |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1172 Byte |
Status |
AC |
Exec Time |
33 ms |
Memory |
6528 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 |
2304 KB |
in10.txt |
AC |
2 ms |
2944 KB |
in11.txt |
AC |
1 ms |
2304 KB |
in12.txt |
AC |
8 ms |
3584 KB |
in13.txt |
AC |
7 ms |
3584 KB |
in14.txt |
AC |
14 ms |
4352 KB |
in15.txt |
AC |
3 ms |
3072 KB |
in16.txt |
AC |
12 ms |
4096 KB |
in17.txt |
AC |
10 ms |
3840 KB |
in18.txt |
AC |
21 ms |
5376 KB |
in19.txt |
AC |
16 ms |
5120 KB |
in2.txt |
AC |
1 ms |
2304 KB |
in20.txt |
AC |
16 ms |
5120 KB |
in21.txt |
AC |
33 ms |
6528 KB |
in22.txt |
AC |
24 ms |
4608 KB |
in23.txt |
AC |
24 ms |
4352 KB |
in24.txt |
AC |
2 ms |
2944 KB |
in25.txt |
AC |
30 ms |
6528 KB |
in26.txt |
AC |
1 ms |
2304 KB |
in27.txt |
AC |
1 ms |
2304 KB |
in28.txt |
AC |
33 ms |
6528 KB |
in3.txt |
AC |
1 ms |
2304 KB |
in4.txt |
AC |
1 ms |
2304 KB |
in5.txt |
AC |
26 ms |
4992 KB |
in6.txt |
AC |
3 ms |
3072 KB |
in7.txt |
AC |
3 ms |
3072 KB |
in8.txt |
AC |
4 ms |
3200 KB |
in9.txt |
AC |
10 ms |
4224 KB |
sample1.txt |
AC |
1 ms |
2304 KB |
sample2.txt |
AC |
1 ms |
2304 KB |