Submission #2234152
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <limits> #include <map> #define REP(i,n) for(long (i)=0;(i)<(n);(i)++) #define INF numeric_limits<double>::infinity() constexpr long MOD = 1e9 + 7; using namespace std; long color[202020]; vector<long> adj[202020]; bool isbip(long src) { for (long i: adj[src]) { if (color[i] == color[src]) return false; if (!color[i]) { if (color[src] == 1) color[i] = 2; if (color[src] == 2) color[i] = 1; bool b = isbip(i); if (!b) return b; } } return true; } int main() { long n, m, a, b; cin >> n >> m; color[0] = 1; REP(i,m) { cin >> a >> b; adj[a-1].push_back(b-1); adj[b-1].push_back(a-1); } bool fl = isbip(0); if (fl) { long c = 0; REP(i,202020) { if (color[i] == 1) c++; } cout << c * (n - c) - m << endl; } else { cout << n * (n - 1) / 2 - m << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - 3 Steps |
User | xuzijian629 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 1113 Byte |
Status | AC |
Exec Time | 94 ms |
Memory | 10368 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 | 3 ms | 6400 KB |
01-02.txt | AC | 3 ms | 6400 KB |
01-03.txt | AC | 3 ms | 6400 KB |
01-04.txt | AC | 3 ms | 6400 KB |
01-05.txt | AC | 3 ms | 6400 KB |
01-06.txt | AC | 3 ms | 6400 KB |
01-07.txt | AC | 3 ms | 6400 KB |
01-08.txt | AC | 4 ms | 6400 KB |
01-09.txt | AC | 4 ms | 6400 KB |
01-10.txt | AC | 5 ms | 6528 KB |
02-01.txt | AC | 87 ms | 9984 KB |
02-02.txt | AC | 91 ms | 9984 KB |
02-03.txt | AC | 89 ms | 9984 KB |
02-04.txt | AC | 94 ms | 9984 KB |
02-05.txt | AC | 92 ms | 9984 KB |
02-06.txt | AC | 91 ms | 9984 KB |
02-07.txt | AC | 85 ms | 9600 KB |
02-08.txt | AC | 88 ms | 9984 KB |
02-09.txt | AC | 87 ms | 9984 KB |
02-10.txt | AC | 56 ms | 9088 KB |
02-11.txt | AC | 71 ms | 9216 KB |
02-12.txt | AC | 90 ms | 9856 KB |
02-13.txt | AC | 87 ms | 10112 KB |
02-14.txt | AC | 93 ms | 10368 KB |
sample-01.txt | AC | 3 ms | 6400 KB |
sample-02.txt | AC | 3 ms | 6400 KB |