Submission #1675840
Source Code Expand
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
// _oo0oo_ //
// o8888888o //
// 88" . "88 ------ hzt1 //
// (| -_- |) //
// 0\ = /0 //
// ___/`---'\___ //
// .' \| |// '. //
// / \||| : |||// \ //
// / _||||| -:- |||||- \ //
// | | \ - /// | | //
// | \_| ''\---/'' |_/ | //
// \ .-\__ '-' ___/-. / //
// ___'. .' /--.--\ `. .'___ //
// ."" '< `.___\_<|>_/___.' >' "". //
// | | : `- \`.;`\ _ /`;.`/ - ` : | | //
// \ \ `_. \_ __\ /__ _/ .-` / / //
// =====`-.____`.___ \_____/___.-`___.-'===== //
// `=---=' //
// //
// //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// //
// God-He Bless All. //
// This Code Will Never Explode. //
// //
// //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,Size,stdin);
tail=(head=buffer)+l;
}
if(head==tail) return -1;
return *head++;
}
inline int read() {
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
typedef long long ll;
const int maxn=100010;
int n,m,pa[maxn],siz[maxn],cnt[maxn];
int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);}
int main() {
n=read();m=read();
rep(i,1,n) pa[i]=i,siz[i]=1;
rep(i,1,m) {
int u=findset(read()),v=findset(read());
if(u==v) cnt[v]++;
else {
pa[u]=v;siz[v]+=siz[u];cnt[v]+=cnt[u]+1;
}
}
ll a=0,b=0,c=0;
rep(i,1,n) if(findset(i)==i) {
if(siz[i]==1) c++;
else if(cnt[i]+1==siz[i]) a++;
else b++;
}
ll ans=0;
ans+=2*a+b+2*a*(a-1)+2*b*a+b*(b-1);
int cur=n-c;
rep(i,1,c) {
ans+=1+2*cur;
cur++;
}
printf("%lld\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Squared Graph |
User |
wzj52501 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3103 Byte |
Status |
WA |
Exec Time |
18 ms |
Memory |
1408 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
896 KB |
in11.txt |
AC |
1 ms |
128 KB |
in12.txt |
AC |
3 ms |
1408 KB |
in13.txt |
AC |
3 ms |
1408 KB |
in14.txt |
AC |
6 ms |
1408 KB |
in15.txt |
AC |
2 ms |
1408 KB |
in16.txt |
AC |
5 ms |
1408 KB |
in17.txt |
WA |
5 ms |
1408 KB |
in18.txt |
WA |
11 ms |
1408 KB |
in19.txt |
AC |
10 ms |
1408 KB |
in2.txt |
AC |
1 ms |
128 KB |
in20.txt |
AC |
10 ms |
1408 KB |
in21.txt |
AC |
17 ms |
1408 KB |
in22.txt |
AC |
6 ms |
384 KB |
in23.txt |
AC |
4 ms |
256 KB |
in24.txt |
AC |
2 ms |
1280 KB |
in25.txt |
AC |
18 ms |
1408 KB |
in26.txt |
AC |
1 ms |
128 KB |
in27.txt |
AC |
1 ms |
128 KB |
in28.txt |
AC |
17 ms |
1408 KB |
in3.txt |
AC |
1 ms |
128 KB |
in4.txt |
AC |
1 ms |
128 KB |
in5.txt |
AC |
8 ms |
1408 KB |
in6.txt |
AC |
2 ms |
1408 KB |
in7.txt |
AC |
2 ms |
1408 KB |
in8.txt |
WA |
2 ms |
1408 KB |
in9.txt |
AC |
6 ms |
1408 KB |
sample1.txt |
AC |
1 ms |
128 KB |
sample2.txt |
AC |
1 ms |
128 KB |