답안 #767595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767595 2023-06-26T22:23:21 Z rainboy 결혼 문제 (IZhO14_marriage) C
66 / 100
583 ms 9388 KB
/* 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

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--;
      |   ^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 0 ms 340 KB Output isn't correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Incorrect 1 ms 468 KB Output isn't correct
20 Incorrect 1 ms 468 KB Output isn't correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Incorrect 2 ms 852 KB Output isn't correct
26 Incorrect 1 ms 724 KB Output isn't correct
27 Correct 1 ms 724 KB Output is correct
28 Correct 1 ms 680 KB Output is correct
29 Correct 2 ms 844 KB Output is correct
30 Correct 2 ms 724 KB Output is correct
31 Incorrect 9 ms 2736 KB Output isn't correct
32 Incorrect 3 ms 2484 KB Output isn't correct
33 Correct 3 ms 1704 KB Output is correct
34 Correct 6 ms 2480 KB Output is correct
35 Correct 38 ms 2876 KB Output is correct
36 Correct 30 ms 2896 KB Output is correct
37 Incorrect 14 ms 4796 KB Output isn't correct
38 Correct 18 ms 4948 KB Output is correct
39 Correct 230 ms 8988 KB Output is correct
40 Correct 140 ms 8752 KB Output is correct
41 Incorrect 151 ms 8936 KB Output isn't correct
42 Correct 38 ms 4784 KB Output is correct
43 Correct 40 ms 4908 KB Output is correct
44 Correct 98 ms 9212 KB Output is correct
45 Incorrect 453 ms 9032 KB Output isn't correct
46 Incorrect 461 ms 9276 KB Output isn't correct
47 Correct 190 ms 9388 KB Output is correct
48 Correct 183 ms 9244 KB Output is correct
49 Incorrect 457 ms 9288 KB Output isn't correct
50 Correct 583 ms 9048 KB Output is correct