Submission #713366

#TimeUsernameProblemLanguageResultExecution timeMemory
713366YENGOYANMarriage questions (IZhO14_marriage)C++17
0 / 100
1587 ms3028 KiB
/* //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\ \\ // // 271828___182845__904523__53602__ \\ \\ 87___47____13______52____66__24_ // // 97___75____72______47____09___36 \\ \\ 999595_____74______96____69___67 // // 62___77____24______07____66__30_ \\ \\ 35___35____47______59____45713__ // // \\ \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\// */ #include <iostream> #include <vector> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <cmath> #include <climits> #include <algorithm> #include <random> #include <queue> #include <deque> #include <iomanip> #include <string> #include <tuple> #include <bitset> #include <chrono> #include <ctime> #include <fstream> #include <stack> #include <cstdio> #include <functional> using namespace std; using LL = long long; const int N = 1e3 + 5; const LL mod = 998244353, inf = 1e18; vector<int> dx = { 1, 0, -1, 0, 1, -1, 1, -1 }; vector<int> dy = { 0, -1, 0, 1, -1, 1, 1, -1 }; void solve() { int n, m, k; cin >> n >> m >> k; vector<vector<int>> gp(n + m); for (int i = 0; i < k; ++i) { int u, v; cin >> u >> v; u += m; gp[--u].push_back(--v); gp[v].push_back(u); } int ans = 0; vector<int> mt(n + m, -1); vector<bool> vis(n + m); function<bool(int, int, int)> kuhn = [&](int u, int l, int r) { if (vis[u]) return 0; vis[u] = 1; for (int& v : gp[u]) { if (v < l || v > r) continue; if (mt[v] == -1 || kuhn(mt[v], l, r)) { mt[v] = u; return 1; } } return 0; }; int l = m - 2, r = n - 1, idx = -1; while (l <= r) { int mid = (l + r) / 2; mt = vector<int>(n + m, -1); int cnt = 0; for (int i = 0; i < m; ++i) { vis = vector<bool>(n + m); cnt += kuhn(i, 0, m + mid); } if(cnt == m){ r = mid; idx = mid; } else { l = mid; } } if (idx == -1) { cout << "0\n"; return; } ans += n - idx; mt = vector<int>(n + m, -1); for (int i = 0; i < m; ++i) { vis = vector<bool>(n + m); kuhn(i, m, idx + m); } for (int i = 0; i < n; ++i) { if (mt[i + m] == -1) { ans += n - idx; continue; } int u = mt[i + m]; while (idx < n) { vis = vector<bool>(n + m); if (kuhn(u, i + 1 + m, idx + m)) break; ++idx; } if (idx == n) break; ans += n - idx; } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //int t; cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...