Submission #1209858

#TimeUsernameProblemLanguageResultExecution timeMemory
1209858AcanikolicMarriage questions (IZhO14_marriage)C++20
52 / 100
1596 ms3280 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 ans = 0; for(int i = 1; i <= n; i++) { for(int j = i; j <= n; j++) { if(max_matching(i, j) == m) ans++; } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...