Submission #69089518

---

Source Code Expand

/*
Author : Mikira
9/6/2025 10:00:24 PM
*/

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;

#define rep(i, a, b) for(int i = a; i < int(b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0,0,1,-1,1,-1,1,-1};
const int dy[8] = {1,-1,0,0,1,-1,-1,1};
const char dch[4] = {'R','L','D','U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;
const int kN = 2e5;
set <int> edge[kN + 5];
set <PII> degreeSet;
int degreeCnt[kN + 5];
int main(){
  fasterios();
  LL n, m; cin >> n >> m;
  
  auto updateDegree = [&](int pos, int val) {
    degreeSet.erase({degreeCnt[pos], pos});
    degreeCnt[pos] += val;
    degreeSet.insert({degreeCnt[pos], pos});
  };
  for(int i = 1;i <= n;i++) {
    degreeSet.insert({0, i});
  }
  for(int i = 1;i <= m;i++) {
    int u, v; cin >> u >> v;
    edge[u].insert(v);
    edge[v].insert(u);
    updateDegree(u, 1);
    updateDegree(v, 1);
  }
  while(prev(degreeSet.end())->fi > 1) {
    auto bridge = prev(degreeSet.end())->se;
    // take the two and change
    auto a = *edge[bridge].begin();
    auto b = *next(edge[bridge].begin());
    edge[a].erase(bridge);
    edge[bridge].erase(a);
    edge[b].erase(bridge);
    edge[bridge].erase(b);
    updateDegree(bridge, -2);
    if(edge[a].count(b)) {
      edge[a].erase(b);
      updateDegree(a, -2);
      edge[b].erase(a);
      updateDegree(b, -2);
    } else {
      edge[a].insert(b);
      edge[b].insert(a);
    }
  }
  LL tot = 0;
  rep(i,1,n + 1) tot += degreeCnt[i];
  if(n%2 == 1) {
    LL ans = (n * (n - 1)) / 2;
    ans -= tot / 2;
    cout << ans << endl;
  } else {
    LL ans = (n * (n - 1)) / 2 - (n / 2);
    ans += tot / 2;
    cout << ans << endl;
  }
  return 0;
}

Submission Info

Judge Result