Submission #767546

#	Time	Username	Problem	Language	Result	Execution time	Memory
767546		rainboy	Marriage questions (IZhO14_marriage)	C11	86 / 100	1592 ms	1324 KiB

marriage

#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, o_;

	visited[v] = 1;
	for (o = 0, o_ = 0; o < eo[v]; o++) {
		int u = eu[v][o], w = vv[u];

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

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 (stderr)

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:51:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d%d", &nu, &nv, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
marriage.c:55:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &u, &v), u--, v--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 86 / 100