Submission #544734

#	Time	Username	Problem	Language	Result	Execution time	Memory
544734		rainboy	Friends (BOI17_friends)	C11	100 / 100	64 ms	6788 KiB

friends

/* https://codeforces.com/blog/entry/51740?#comment-356943 (mnbvmar) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	2500
#define P	15

int *ej[N], eo[N], qu[N], qu1[N], hh[N], cnt1, n, p_, q_; char visited[N], in[N];

int branch(int head, int cnt, int p, int q) {
	int i, o, d, cnt_;

	if (cnt == 0) {
		cnt1 = 0;
		for (i = 0; i < n; i++)
			if (in[i])
				in[i] = 0, visited[i] = 1, qu1[cnt1++] = i;
		return 1;
	}
	i = qu[cnt--, head++];
	d = 0;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		if (in[j] == 1)
			d++;
	}
	if (head > 1 && q + d <= q_ && branch(head, cnt, p, q + d))
		return 1;
	if (p == p_)
		return 0;
	in[i] = 1;
	cnt_ = cnt;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		if (hh[j] == -1) {
			if (head + cnt == p_ + q_) {
				in[i] = 0;
				while (cnt > cnt_)
					hh[qu[head + --cnt]] = -1;
				return 0;
			}
			hh[j] = head + cnt, qu[head + cnt++] = j;
		} else if (hh[j] < head && !in[j] && q++ == q_) {
			in[i] = 0;
			while (cnt > cnt_)
				hh[qu[head + --cnt]] = -1;
			return 0;
		}
	}
	if (branch(head, cnt, p + 1, q))
		return 1;
	in[i] = 0;
	while (cnt > cnt_)
		hh[qu[head + --cnt]] = -1;
	return 0;
}

int main() {
	static int qu_[N][P], cnt_[N];
	static char aa[N][N], in1[N], in2[N];
	int g, h, i, j, k;

	scanf("%d%d%d", &n, &p_, &q_);
	for (i = 0; i < n; i++) {
		int m;

		scanf("%d", &m);
		ej[i] = (int *) malloc(m * sizeof *ej[i]);
		while (m--) {
			scanf("%d", &j);
			ej[i][eo[i]++] = j;
			aa[i][j] = 1;
		}
	}
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (aa[i][j] != aa[j][i]) {
				printf("detention\n");
				return 0;
			}
	for (i = 0; i < n; i++)
		if (!visited[i]) {
			memset(hh, -1, n * sizeof *hh);
			hh[i] = 0, qu[0] = i;
			if (!branch(0, 1, 0, 0)) {
				printf("detention\n");
				return 0;
			}
			memcpy(qu_[i], qu1, (cnt_[i] = cnt1) * sizeof *qu_[i]);
		}
	for (j = 0; j < n; j++)
		for (i = 0; i < j; i++) {
			int d, i_, j_, o;

			for (g = 0; g < cnt_[i]; g++) {
				i_ = qu_[i][g];
				in1[i_] = 1;
			}
			for (h = 0; h < cnt_[j]; h++) {
				j_ = qu_[j][h];
				in2[j_] = 1;
			}
			d = 0;
			for (g = 0; g < cnt_[i]; g++) {
				i_ = qu_[i][g];
				if (in2[i_])
					for (o = 0; o < eo[i_]; o++) {
						j_ = ej[i_][o];
						if (in1[j_])
							d++;
						if (in2[j_])
							d--;
					}
			}
			if (d < 0) {
				cnt1 = 0;
				for (g = 0; g < cnt_[i]; g++) {
					i_ = qu_[i][g];
					if (!in2[i_])
						qu_[i][cnt1++] = i_;
					else
						in1[i_] = 0;
				}
				cnt_[i] = cnt1;
			} else {
				cnt1 = 0;
				for (h = 0; h < cnt_[j]; h++) {
					j_ = qu_[j][h];
					if (!in1[j_])
						qu_[j][cnt1++] = j_;
					else
						in2[j_] = 0;
				}
				cnt_[j] = cnt1;
			}
			for (g = 0; g < cnt_[i]; g++) {
				i_ = qu_[i][g];
				in1[i_] = 0;
			}
			for (h = 0; h < cnt_[j]; h++) {
				j_ = qu_[j][h];
				in2[j_] = 0;
			}
		}
	k = 0;
	for (i = 0; i < n; i++)
		if (cnt_[i])
			k++;
	printf("home\n");
	printf("%d\n", k);
	for (i = 0; i < n; i++)
		if (cnt_[i]) {
			printf("%d", cnt_[i]);
			while (cnt_[i]--)
				printf(" %d", qu_[i][cnt_[i]]);
			printf("\n");
		}
	return 0;
}

Compilation message (stderr)

friends.c: In function 'main':
friends.c:66:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d%d%d", &n, &p_, &q_);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
friends.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d", &m);
      |   ^~~~~~~~~~~~~~~
friends.c:73:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |    scanf("%d", &j);
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 37 / 37
• Subtask 3: 12 / 12
• Subtask 4: 31 / 31