Submission #4064765
Source Code Expand
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;
struct edge {
ll to, cost;
};
int V;
vector<edge> G[1000000];
ll d[1000000];
void addedge(int st, int ed, ll co) {
edge e;
e.to = ed;
e.cost = co;
G[st].push_back(e);
}
bool bipartite() {
fill(d, d + V, -1);
while (true) {
int num = 0;
for (int i = num; i < V; i++) {
if (d[num] == -1) {
break;
}
num++;
}
if (num == V) {
return true;
}
d[num] = 0;
queue<int> que;
que.push(num);
while (que.size() > 0) {
int base = que.front();
que.pop();
int s = G[base].size();
for (int i = 0; i < s; i++) {
int to = G[base][i].to;
if (d[to] == -1) {
if (d[base] == 0) {
d[to] = 1;
} else {
d[to] = 0;
}
que.push(to);
} else {
if (d[to] == 1 && d[base] == 1) {
return false;
} else if (d[to] == 0 && d[base] == 0) {
return false;
}
}
}
}
}
}
int main() {
ll N, M;
cin >> N >> M;
V = N;
REP(i, 0, M) {
ll a, b;
cin >> a >> b;
addedge(a - 1, b - 1, 1);
addedge(b - 1, a - 1, 1);
}
bool ok = bipartite();
if (ok) {
ll zero = 0, one = 0;
REP(i, 0, N) {
if (d[i] == 0) {
zero++;
} else {
one++;
}
}
cout << zero * one - M << endl;
} else {
cout << N * (N - 1) / 2 - M << endl;
}
}
Submission Info
Submission Time |
|
Task |
C - 3 Steps |
User |
NMLibrary |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
3163 Byte |
Status |
AC |
Exec Time |
96 ms |
Memory |
31360 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
500 / 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 |
11 ms |
25344 KB |
01-02.txt |
AC |
11 ms |
25344 KB |
01-03.txt |
AC |
11 ms |
25344 KB |
01-04.txt |
AC |
11 ms |
25344 KB |
01-05.txt |
AC |
11 ms |
25344 KB |
01-06.txt |
AC |
11 ms |
25472 KB |
01-07.txt |
AC |
11 ms |
25344 KB |
01-08.txt |
AC |
11 ms |
25344 KB |
01-09.txt |
AC |
12 ms |
25472 KB |
01-10.txt |
AC |
13 ms |
25600 KB |
02-01.txt |
AC |
90 ms |
31360 KB |
02-02.txt |
AC |
89 ms |
31360 KB |
02-03.txt |
AC |
92 ms |
31360 KB |
02-04.txt |
AC |
93 ms |
31360 KB |
02-05.txt |
AC |
93 ms |
31360 KB |
02-06.txt |
AC |
90 ms |
31360 KB |
02-07.txt |
AC |
87 ms |
30976 KB |
02-08.txt |
AC |
89 ms |
31360 KB |
02-09.txt |
AC |
89 ms |
31360 KB |
02-10.txt |
AC |
59 ms |
30848 KB |
02-11.txt |
AC |
71 ms |
30592 KB |
02-12.txt |
AC |
85 ms |
30976 KB |
02-13.txt |
AC |
86 ms |
31360 KB |
02-14.txt |
AC |
96 ms |
31360 KB |
sample-01.txt |
AC |
11 ms |
25344 KB |
sample-02.txt |
AC |
11 ms |
25344 KB |