Submission #713619

#TimeUsernameProblemLanguageResultExecution timeMemory
713619alex_2008Marriage questions (IZhO14_marriage)C++14
86 / 100
488 ms4252 KiB
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <cmath> using namespace std; const int N = 50050; 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 (auto it : g[v]) { if (it >= L && it <= R) { if (mt[it] == -1 || kuhn(mt[it], L, R)) { mt[it] = v; return true; } } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); 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); } int l = m, r = n, ind = -1; while (l <= r) { int mid = (l + r) / 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; } if (kuhn(i, 1, mid + m)) ++cnt; } if (cnt == m) { ind = mid; r = mid - 1; } else l = mid + 1; } if (ind == -1) { cout << "0\n"; 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, 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; } if (kuhn(girl, i + 1, ind + m)) break; ind++; } if (ind == n + 1) break; answ += n - ind + 1; } cout << answ << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...