Submission #711318

#	Time	Username	Problem	Language	Result	Execution time	Memory
711318		LeMur	Marriage questions (IZhO14_marriage)	C++14	100 / 100	439 ms	3284 KiB

marriage

///////////////////////////////    _LeMur_
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <tuple>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 50005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;
// mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
mt19937 myrand(1337);

int n, m, k;
vector <int> g[N];

bool used[N];
int mt[N];

bool kuhn(int v, int L, int R) {
  if (used[v]) return false;
  used[v] = true;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i];
    if (to < L) continue;
    if (to > R) break;
    if (mt[to] == -1 || kuhn(mt[to], L, R)) {
      mt[to] = v;
      return true;
    }
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m >> k;

  for (int i = 1; i <= k; i++) {
    int a, b;
    cin >> a >> b;
    a += m;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  for (int i = 1; i <= m; i++) {
    sort(g[i].begin(), g[i].end());
  }

  int ina = m, inb = n, ind = -1;
  while (ina <= inb) {
    int mid = (ina + inb) / 2;

    for (int i = 1; i <= mid; i++) {
      mt[i + m] = -1;
    }

    int cnt = 0;
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= m; j++) {
        used[j] = false;
      }
      bool flag = kuhn(i, 1, mid + m);
      if (flag) ++cnt;
    }

    if (cnt == m) {
      ind = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }

  if (ind == -1) {
    cout << 0 << endl;
    return 0;
  }

  for (int i = 1; i <= n; i++) {
    mt[i + m] = -1;
  }

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= m; j++) {
      used[j] = false;
    }
    kuhn(i, 1 + m, ind + m);
  }

  int answ = n - ind + 1;

  for (int i = 1; i <= n; i++) {
    if (mt[i + m] == -1) {
      answ += n - ind + 1;
      continue;
    }

    int girl = mt[i + m];
    while (ind <= n) {
      for (int j = 1; j <= m; j++) {
        used[j] = false;
      }
      bool flag = kuhn(girl, i + 1 + m, ind + m);
      if (flag) break;
      ++ind;
    }
    
    if (ind == n + 1) break;
    answ += n - ind + 1;
  }
  
  cout << answ << endl;
  return 0;
}

• Subtask 1: 100 / 100