Submission #1209859

#TimeUsernameProblemLanguageResultExecution timeMemory
1209859AcanikolicMarriage questions (IZhO14_marriage)C++20
62 / 100
1595 ms2520 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e4 + 10; const int M = 2010; bool was[N + M]; int n, m, k, mt[N + M]; vector<int> g[N + M]; vector<pair<int, int>> e; bool kuhn(int x) { if(was[x]) return false; was[x] = true; for(int j : g[x]) { if(mt[j] == -1 || kuhn(mt[j])) { mt[j] = x; return true; } } return false; } int max_matching(int l, int r) { for(int i = 1; i <= n + m; i++) { was[i] = false; mt[i] = -1; g[i].clear(); } for(auto x : e) { if(x.first >= l && x.first <= r) { g[x.second].push_back(x.first + m); g[x.first + m].push_back(x.second); } } for(int i = 1; i <= m; i++) { for(int j = 1; j <= m; j++) was[j] = false; kuhn(i); } int cnt = 0; for(int i = 1; i <= n + m; i++) if(mt[i] != -1) cnt++; return cnt; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; for(int i = 1; i <= k; i++) { int u, v; cin >> u >> v; e.push_back({u, v}); } int res = 0; for(int i = 1; i <= n; i++) { int l = 1, r = i, ans = -1; while(l <= r) { int mid = l + r >> 1; if(max_matching(mid, i) == m) { ans = mid; l = mid + 1; } else { r = mid - 1; } } if(ans == -1) continue; res += ans; } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...