Submission #544730

#	Time	Username	Problem	Language	Result	Execution time	Memory
544730		rainboy	Political Development (BOI17_politicaldevelopment)	C11	100 / 100	80 ms	6264 KiB

politicaldevelopment

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

#define N	50000
#define K	10

int *ej[N], eo[N], qu[K + 1][N], cnt[K + 1], dd[N], ans, k_;

void solve(int k) {
	int h;

	if (k + cnt[k] < ans)
		return;
	if (k == k_) {
		printf("%d\n", k_);
		exit(0);
	}
	if (ans < k)
		ans = k;
	for (h = 0; h < cnt[k]; h++) {
		int i = qu[k][h], o;

		cnt[k + 1] = 0;
		for (o = 0; o < eo[i]; o++) {
			int j = ej[i][o];

			if (dd[j] == k)
				dd[j]++, qu[k + 1][cnt[k + 1]++] = j;
		}
		solve(k + 1);
		for (o = 0; o < eo[i]; o++) {
			int j = ej[i][o];

			if (dd[j] == k + 1)
				dd[j]--;
		}
	}
}

int main() {
	int n, i, j, head;

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

		scanf("%d", &d), dd[i] = d;
		ej[i] = (int *) malloc((eo[i] = d) * sizeof *ej[i]);
		while (d--) {
			scanf("%d", &j);
			ej[i][d] = j;
		}
	}
	head = 0;
	for (i = 0; i < n; i++)
		if (dd[i] <= k_)
			qu[0][head + cnt[0]++] = i;
	while (cnt[0]) {
		int o, d;

		i = qu[0][cnt[0]--, head++], dd[i] = -1;
		d = 0;
		for (o = 0; o < eo[i]; o++) {
			int j = ej[i][o];

			if (dd[j] >= 0) {
				ej[i][d++] = j;
				if (--dd[j] == k_)
					qu[0][head + cnt[0]++] = j;
			}
		}
		eo[i] = d;
	}
	memset(dd, 0, n * sizeof *dd);
	cnt[0] = n;
	solve(0);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

politicaldevelopment.c: In function 'main':
politicaldevelopment.c:45:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d", &n, &k_);
      |  ^~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d", &d), dd[i] = d;
      |   ^~~~~~~~~~~~~~~
politicaldevelopment.c:52:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |    scanf("%d", &j);
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23