# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
899213 | MilosMilutinovic | Marriage questions (IZhO14_marriage) | C++14 | 1595 ms | 4000 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.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(m);
vector<vector<int>> r(n);
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
--x; --y;
g[y].push_back(x);
r[x].push_back(y);
}
for (int i = 0; i < m; i++) {
sort(g[i].begin(), g[i].end());
}
vector<int> f(m);
int ptr = 0;
auto Good = [&]() {
vector<bool> used(m);
vector<int> to(n, -1);
function<bool(int)> Dfs = [&](int v) {
if (used[v]) {
return false;
}
used[v] = true;
for (int j = f[v]; j < (int) g[v].size(); j++) {
if (g[v][j] > ptr) {
break;
}
if (to[g[v][j]] == -1 || Dfs(to[g[v][j]])) {
to[g[v][j]] = v;
return true;
}
}
return false;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
used[j] = false;
}
Dfs(i);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (to[i] != -1) {
cnt += 1;
}
}
return cnt == m;
};
long long res = 0;
for (int i = 0; i < n; i++) {
while (ptr < n && (ptr - i + 1 < m || !Good())) {
ptr += 1;
}
res += n - ptr;
for (int j : r[i]) {
f[j] += 1;
}
}
cout << res << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |