Submission #3016236
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<signed(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const ll INF = 20000000000;
typedef std::pair<int,int> P;
ll ans=0;
ll N,M,K,G,A[500010],B[500010];
ll sum;bool F=true;
string S;
struct UnionFind {
vector< int > data;
UnionFind(int sz){
data.assign(sz, -1);
}
bool unite(int x, int y){
x = find(x), y = find(y);
if(x == y) return(false);
if(data[x] > data[y]) std::swap(x, y);
data[x] += data[y];
data[y] = x;
return(true);
}
int find(int k){
if(data[k] < 0) return(k);
return(data[k] = find(data[k]));
}
bool same(int x,int y){
return find(x)==find(y);
}
int size(int k){
return(-data[find(k)]);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin>>N>>M;
UnionFind U(2*N);
REP(i,M){
int a,b;
cin>>a>>b;a--,b--;
U.unite(a,b+N);
U.unite(a+N,b);
}
REP(i,M){
if(U.same(i,i+N)){
cout<<N*(N-1)/2-M<<endl;
return 0;
}
}
ll cnt=0;
REP(i,N){
if(U.same(0,i))cnt++;
}
cout<<cnt*(N-cnt)-M;
}
Submission Info
Submission Time |
|
Task |
C - 3 Steps |
User |
Nafmo2 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1822 Byte |
Status |
RE |
Exec Time |
99 ms |
Memory |
1024 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
all |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
1 ms |
256 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
1 ms |
256 KB |
01-04.txt |
AC |
1 ms |
256 KB |
01-05.txt |
AC |
1 ms |
256 KB |
01-06.txt |
AC |
1 ms |
256 KB |
01-07.txt |
RE |
99 ms |
256 KB |
01-08.txt |
WA |
1 ms |
256 KB |
01-09.txt |
WA |
2 ms |
256 KB |
01-10.txt |
AC |
2 ms |
256 KB |
02-01.txt |
AC |
21 ms |
1024 KB |
02-02.txt |
AC |
21 ms |
1024 KB |
02-03.txt |
AC |
21 ms |
1024 KB |
02-04.txt |
AC |
22 ms |
1024 KB |
02-05.txt |
AC |
22 ms |
1024 KB |
02-06.txt |
AC |
21 ms |
1024 KB |
02-07.txt |
AC |
21 ms |
640 KB |
02-08.txt |
AC |
21 ms |
1024 KB |
02-09.txt |
AC |
21 ms |
1024 KB |
02-10.txt |
WA |
16 ms |
256 KB |
02-11.txt |
WA |
17 ms |
384 KB |
02-12.txt |
WA |
20 ms |
640 KB |
02-13.txt |
WA |
20 ms |
896 KB |
02-14.txt |
WA |
22 ms |
1024 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |