# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
713377 | YENGOYAN | Marriage questions (IZhO14_marriage) | C++17 | 866 ms | 3032 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 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, idx = -1;
while (l + 1 < 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |