Submission #2526096
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define X first #define Y second #define pb push_back #define CL(x) (x << 1) #define CR(x) ((x << 1) + 1) #define sqr(x) ((x) * (x)) #define Task "" typedef long long cc; typedef long double ld; typedef pair <int, int> pii; const int N = 100005; vector <int> e[N]; bool le[N], chan[N]; int n, m; int res; bool was[N]; int odd, even; bool ok; void dfs(int u, int p) { was[u] = true; if (le[u]) odd++; if (chan[u]) even++; if (le[u] && chan[u]) ok = true; for (auto v: e[u]) if (v != u) { le[v] = le[v] | (chan[u] & 1); chan[v] = chan[v] | (le[u] & 1); if (!was[v]) dfs(v, u); } } int main() { std :: ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //freopen("input.inp", "r", stdin); //------------------------------------------------------------------------------------------------------- cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[u].pb(v); e[v].pb(u); } le[1] = 1; dfs(1, -1); for (int i = 1; i <= n; i++) ok = ok | (le[i] && chan[i]); if (ok) cout << 1ll * n * (n - 1) / 2 - m; else { cc tmp = 0; for (int i = 1; i <= n; i++) { if (!le[i]) tmp += 1ll * even - 1; if (!chan[i]) tmp += 1ll * odd - 1; } cout << max(0ll, 1ll * n * (n - 1) / 2 - m - tmp / 2); } //------------------------------------------------------------------------------------------------------- return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 3 Steps |
User | AnyOneCrushMe |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 1684 Byte |
Status | AC |
Exec Time | 42 ms |
Memory | 6912 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 | 2 ms | 2560 KB |
01-02.txt | AC | 2 ms | 2560 KB |
01-03.txt | AC | 2 ms | 2560 KB |
01-04.txt | AC | 2 ms | 2560 KB |
01-05.txt | AC | 2 ms | 2688 KB |
01-06.txt | AC | 3 ms | 2688 KB |
01-07.txt | AC | 2 ms | 2688 KB |
01-08.txt | AC | 2 ms | 2688 KB |
01-09.txt | AC | 3 ms | 2688 KB |
01-10.txt | AC | 3 ms | 2688 KB |
02-01.txt | AC | 41 ms | 6784 KB |
02-02.txt | AC | 41 ms | 6144 KB |
02-03.txt | AC | 40 ms | 6144 KB |
02-04.txt | AC | 41 ms | 6144 KB |
02-05.txt | AC | 42 ms | 6144 KB |
02-06.txt | AC | 41 ms | 6144 KB |
02-07.txt | AC | 36 ms | 6400 KB |
02-08.txt | AC | 41 ms | 6912 KB |
02-09.txt | AC | 41 ms | 6400 KB |
02-10.txt | AC | 18 ms | 4096 KB |
02-11.txt | AC | 25 ms | 4352 KB |
02-12.txt | AC | 36 ms | 5504 KB |
02-13.txt | AC | 34 ms | 6016 KB |
02-14.txt | AC | 40 ms | 6528 KB |
sample-01.txt | AC | 2 ms | 2560 KB |
sample-02.txt | AC | 2 ms | 2560 KB |