Submission #767599

#	Time	Username	Problem	Language	Result	Execution time	Memory
767599		rainboy	Marriage questions (IZhO14_marriage)	C11	66 / 100	769 ms	9256 KiB

marriage

/* https://oj.uz/submission/100855 (Benq) */
#include <stdio.h>
#include <string.h>

#define NU	30000
#define NV	4000

int nu, nv;
int eu[NV][NU], eo[NV], 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]++;
		}
		ans += nu - r;
		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;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

marriage.c: In function 'main':
marriage.c:44:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d%d%d", &nu, &nv, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
marriage.c:46:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d", &u, &v), u--, v--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 66 / 100