oj.uz

답안 #767543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767543 2023-06-26T20:28:22 Z rainboy 결혼 문제 (IZhO14_marriage) C
60 / 100
 1500 ms 2176 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NU	30000
#define NV	2000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int nu, nv;

int *eu[NV], eo[NV];

void append(int v, int u) {
	int o = eo[v]++;

	if (o >= 2 && (o & o - 1) == 0)
		eu[v] = (int *) realloc(eu[v], o * 2 * sizeof *eu[v]);
	eu[v][o] = u;
}

int l, u_;

int uu[NV], vv[NU], pp[NU]; char visited[NV];

void dfs(int v) {
	int o;

	visited[v] = 1;
	for (o = eo[v]; o--; ) {
		int u = eu[v][o], w = vv[u];

		if (u <= l)
			break;
		if (w == -1 || !visited[w]) {
			pp[u] = v;
			if (w == -1)
				u_ = min(u_, u);
			else
				dfs(w);
		}
	}
}

int main() {
	int m, u, v, v_, r, ans;

	scanf("%d%d%d", &nu, &nv, &m);
	for (v = 0; v < nv; v++)
		eu[v] = (int *) malloc(2 * sizeof *eu[v]);
	while (m--) {
		scanf("%d%d", &u, &v), u--, v--;
		append(v, u);
	}
	memset(uu, -1, nv * sizeof *uu), memset(vv, -1, nu * sizeof *vv);
	for (v = 0; v < nv; v++) {
		memset(visited, 0, nv * sizeof *visited);
		l = -1, u_ = nu, dfs(v);
		u = u_;
		while (1) {
			v_ = pp[u], u_ = uu[v_];
			uu[v_] = u, vv[u] = v_;
			u = u_;
			if (v_ == v)
				break;
		}
	}
	r = -1;
	for (v = 0; v < nv; v++)
		r = max(r, uu[v]);
	ans = 0;
	for (u = 0; u < nu; u++) {
		ans += nu - r;
		if ((v = vv[u]) != -1) {
			memset(visited, 0, nv * sizeof *visited);
			l = u, u_ = nu, dfs(v);
			if (u_ == nu)
				break;
			r = max(r, u_);
			u = u_;
			while (1) {
				v_ = pp[u], u_ = uu[v_];
				uu[v_] = u, vv[u] = v_;
				u = u_;
				if (v_ == v)
					break;
			}
			vv[u] = -1;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

marriage.c: In function 'append':
marriage.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
marriage.c: In function 'main':
marriage.c:49:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d%d", &nu, &nv, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
marriage.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &u, &v), u--, v--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 288 KB Output isn't correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 288 KB Output is correct
7 Incorrect 0 ms 284 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Execution timed out 1571 ms 292 KB Time limit exceeded
13 Correct 1 ms 284 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Execution timed out 1574 ms 212 KB Time limit exceeded
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Incorrect 4 ms 468 KB Output isn't correct
26 Incorrect 1 ms 296 KB Output isn't correct
27 Execution timed out 1581 ms 284 KB Time limit exceeded
28 Correct 1 ms 212 KB Output is correct
29 Correct 4 ms 340 KB Output is correct
30 Correct 3 ms 360 KB Output is correct
31 Incorrect 72 ms 992 KB Output isn't correct
32 Incorrect 7 ms 424 KB Output isn't correct
33 Execution timed out 1574 ms 288 KB Time limit exceeded
34 Correct 2 ms 340 KB Output is correct
35 Correct 41 ms 1716 KB Output is correct
36 Correct 29 ms 1456 KB Output is correct
37 Incorrect 140 ms 1260 KB Output isn't correct
38 Correct 26 ms 1620 KB Output is correct
39 Correct 28 ms 548 KB Output is correct
40 Execution timed out 1584 ms 596 KB Time limit exceeded
41 Incorrect 5 ms 724 KB Output isn't correct
42 Correct 7 ms 812 KB Output is correct
43 Correct 14 ms 1108 KB Output is correct
44 Correct 22 ms 1844 KB Output is correct
45 Incorrect 5 ms 1108 KB Output isn't correct
46 Incorrect 45 ms 2056 KB Output isn't correct
47 Correct 34 ms 2120 KB Output is correct
48 Correct 24 ms 2024 KB Output is correct
49 Incorrect 83 ms 2176 KB Output isn't correct
50 Correct 28 ms 688 KB Output is correct