Submission #491094

#	Time	Username	Problem	Language	Result	Execution time	Memory
491094		rainboy	Izlet (COI19_izlet)	C11	100 / 100	1343 ms	74480 KiB

izlet

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	3000

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int aa[N][N];

void dfs(int p, int r, int s, int i) {
	int o;

	if (s != -1 && aa[r][i] == aa[s][i])
		join(r, i);
	else
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (j != p)
				dfs(i, r, s == -1 ? j : s, j);
		}
}

int main() {
	static int ii[N - 1], jj[N - 1];
	int n, m, h, i, j, s;

	scanf("%d%d", &s, &n);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &aa[i][j]);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	m = 0;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (aa[i][j] == 1 && join(i, j)) {
				append(i, j), append(j, i);
				ii[m] = i, jj[m] = j, m++;
			}
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (aa[i][j] == 2 && join(i, j)) {
				append(i, j), append(j, i);
				ii[m] = i, jj[m] = j, m++;
			}
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		dfs(-1, i, -1, i);
	for (i = 0; i < n; i++)
		printf("%d ", find(i) + 1);
	printf("\n");
	for (h = 0; h < n - 1; h++)
		printf("%d %d\n", ii[h] + 1, jj[h] + 1);
	return 0;
}

Compilation message (stderr)

izlet.c: In function 'append':
izlet.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
izlet.c: In function 'main':
izlet.c:58:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d%d", &s, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
izlet.c:61:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |    scanf("%d", &aa[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57