Submission #2237520
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; struct BipartiteGraph { int N; vector<vector<int>> G; vector<int> coler; BipartiteGraph() {} BipartiteGraph(int N) : N(N), G(N), coler(N) {} void add_edge(int s, int t) { G[s].emplace_back(t); } bool is_bipartite_graph() { for (int i = 0; i < N; i++) coler[i] = 0; for (int i = 0; i < N; i++) { if (coler[i]) continue; int c = 1; coler[i] = c; stack<int> S; S.emplace(i); while (!S.empty()) { int v = S.top(); S.pop(); for (auto &u : G[v]) { if (coler[u] == coler[v]) return false; if (coler[u]) continue; coler[u] = -coler[v]; S.emplace(u); } } } return true; } pii get_count() { if (!is_bipartite_graph()) return pii(-1, -1); int b = 0, w = 0; for (int i = 0; i < N; i++) b += coler[i] > 0, w += coler[i] < 0; return pii(b, w); } }; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(10); int N, M; cin >> N >> M; BipartiteGraph BG(N); for (int i = 0; i < M; i++) { int A, B; cin >> A >> B; A--, B--; BG.add_edge(A, B); BG.add_edge(B, A); } pii p = BG.get_count(); cout << (p != pii(-1, -1) ? (ll)p.first * p.second - M : (ll)N * (N - 1) / 2 - M) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 3 Steps |
User | legosuke |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 1478 Byte |
Status | AC |
Exec Time | 39 ms |
Memory | 6272 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 | 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 | AC | 1 ms | 256 KB |
01-08.txt | AC | 1 ms | 256 KB |
01-09.txt | AC | 2 ms | 256 KB |
01-10.txt | AC | 2 ms | 384 KB |
02-01.txt | AC | 33 ms | 5632 KB |
02-02.txt | AC | 35 ms | 6144 KB |
02-03.txt | AC | 35 ms | 6144 KB |
02-04.txt | AC | 38 ms | 6144 KB |
02-05.txt | AC | 39 ms | 6144 KB |
02-06.txt | AC | 36 ms | 6144 KB |
02-07.txt | AC | 31 ms | 3712 KB |
02-08.txt | AC | 33 ms | 5632 KB |
02-09.txt | AC | 31 ms | 6144 KB |
02-10.txt | AC | 16 ms | 1664 KB |
02-11.txt | AC | 24 ms | 2048 KB |
02-12.txt | AC | 34 ms | 3712 KB |
02-13.txt | AC | 32 ms | 5760 KB |
02-14.txt | AC | 38 ms | 6272 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |