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
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 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