# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
767595 | rainboy | Marriage questions (IZhO14_marriage) | C11 | 583 ms | 9388 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.
/* https://oj.uz/submission/100855 (Benq) */
#include <stdio.h>
#include <string.h>
#define NU 30000
#define NV 2000
int nu, nv;
int eu[NV][NU], eo[NU], el[NV], er[NV];
int uu[NV], vv[NU]; char visited[NV];
int dfs(int v) {
int o;
if (visited[v])
return 0;
visited[v] = 1;
for (o = el[v]; o < er[v]; o++) {
int u = eu[v][o], w = vv[u];
if (w == -1 || dfs(w)) {
uu[v] = u, vv[u] = v;
return 1;
}
}
return 0;
}
int check() {
int v;
for (v = 0; v < nv; v++)
if (uu[v] == -1) {
memset(visited, 0, nv * sizeof *visited);
if (!dfs(v))
return 0;
}
return 1;
}
int main() {
int m, h, l, r, u, v, ans;
scanf("%d%d%d", &nu, &nv, &m);
for (h = 0; h < m; h++) {
scanf("%d%d", &u, &v), u--, v--;
eu[v][eo[v]++] = u;
}
memset(uu, -1, nv * sizeof *uu), memset(vv, -1, nu * sizeof *vv);
ans = 0;
for (l = 0, r = -1; l < nu; l++) {
while (r < nu && !check()) {
r++;
for (v = 0; v < nv; v++)
if (er[v] < eo[v] && eu[v][er[v]] == r)
er[v]++;
}
for (v = 0; v < nv; v++) {
if (el[v] < eo[v] && eu[v][el[v]] == l)
el[v]++;
if (uu[v] == l)
uu[v] = -1;
}
ans += nu - r;
}
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |