Submission #990219

#	Time	Username	Problem	Language	Result	Execution time	Memory
990219		MilosMilutinovic	Marriage questions (IZhO14_marriage)	C++14	100 / 100	442 ms	2152 KiB

marriage

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> g(m);
  for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[b].push_back(a);
  }
  for (int i = 0; i < m; i++) {
    sort(g[i].begin(), g[i].end());
  }
  vector<int> par(n, -1);
  vector<int> mtc(m, -1);
  vector<int> dfn(m);
  int ptr = -1;
  int T = 0;
  function<bool(int)> Match = [&](int v) {
    if (dfn[v] == T) {
      return false;
    }
    dfn[v] = T;
    for (int u : g[v]) {
      if (u > ptr) {
        continue;
      }
      if (par[u] == -1 || Match(par[u])) {
        par[u] = v;
        mtc[v] = u;
        return true;
      }
    }
    return false;
  };
  long long res = 0;
  vector<int> que;
  for (int i = 0; i < m; i++) {
    que.emplace_back(i);
  }
  for (int i = 0; i < n; i++) {
    while (ptr + 1 < n && !que.empty()) {
      ptr += 1;
      while (!que.empty()) {
        T += 1;
        int v = que.back();
        if (Match(v)) {
          que.pop_back();
        } else {
          break;
        }
      }
    }
    if (que.empty()) {
      res += n - ptr;
    }
    if (par[i] != -1) {
      for (int j = 0; j < m; j++) {
        if (!g[j].empty() && g[j][0] == i) {
          vector<int> new_g;
          for (int k = 1; k < (int) g[j].size(); k++) {
            new_g.push_back(g[j][k]);
          }
          g[j] = new_g;
        }
      }
      T += 1;
      mtc[par[i]] = -1;
      Match(par[i]);
      if (mtc[par[i]] == -1) {
        que.push_back(par[i]);
        mtc[par[i]] = -1;
      }
    }
  }
  cout << res << '\n';
  return 0;
}

• Subtask 1: 100 / 100