Submission #2521846


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 (chan[i]) tmp += 1ll * even - 1;
            if (le[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 40 ms
Memory 6912 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 28
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 2560 KB
01-06.txt AC 2 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 40 ms 6784 KB
02-02.txt AC 40 ms 6144 KB
02-03.txt AC 40 ms 6144 KB
02-04.txt AC 40 ms 6144 KB
02-05.txt AC 40 ms 6144 KB
02-06.txt AC 40 ms 6144 KB
02-07.txt AC 36 ms 6272 KB
02-08.txt AC 40 ms 6912 KB
02-09.txt AC 40 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 33 ms 6016 KB
02-14.txt AC 39 ms 6528 KB
sample-01.txt AC 2 ms 2560 KB
sample-02.txt AC 2 ms 2560 KB