# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91348 | Just_Solve_The_Problem | Marriage questions (IZhO14_marriage) | C++11 | 1583 ms | 4644 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;
#define ok puts("ok");
#define ll long long
const int N = (int)2e3 + 7;
int n, m, k;
vector < int > gr[N];
pair < int, int > lr[N];
int used[N], mt[(int)3e4 + 7], prr[N], cnt = 1;
int val;
bool kuhn(int v) {
if (used[v] == cnt) return false;
used[v] = cnt;
for (int i = lr[v].first; i < gr[v].size(); i++) {
int to = gr[v][i];
if (to > val) break;
if (mt[to] == -1 || kuhn(mt[to])) {
mt[to] = v;
prr[v] = to;
return true;
}
}
return false;
}
int check(int l) {
for (int i = 1; i <= m; i++) {
while (lr[i].first < (int)gr[i].size() && gr[i][lr[i].first] < l) lr[i].first++;
}
memset(mt, -1, sizeof mt);
memset(prr, -1, sizeof prr);
int run = 1;
while (run) {
run = 0;
for (int i = 1; i <= m; i++) {
if (prr[i] == -1 && kuhn(i)) {
run = 1;
}
}
cnt++;
}
int mx = 0;
for (int i = 1; i <= m; i++) {
if (prr[i] == -1) {
return n + 1;
}
mx = max(mx, prr[i]);
}
return mx;
}
main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= k; i++) {
int a, b;
scanf("%d %d", &a, &b);
gr[b].push_back(a);
}
ll ans = 0;
for (int i = 1; i <= m; i++) {
sort(gr[i].begin(), gr[i].end());
lr[i].first = 0;
}
for (int i = 1; i <= n - m + 1; i++) {
int l = i;
int r = n + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
val = mid;
int res = check(i);
if (res != n + 1) {
r = res;
} else {
l = mid;
}
}
//cout << i << ' ' << r << endl;
ans += (n - r + 1);
}
cout << ans << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |