oj.uz

Submission #491094

# Submission time Handle Problem Language Result Execution time Memory
491094 2021-11-30T14:06:09 Z rainboy Izlet (COI19_izlet) C
100 / 100
 1343 ms 74480 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1343 ms 44476 KB Output is correct
3 Correct 893 ms 43780 KB Output is correct
4 Correct 863 ms 44984 KB Output is correct
5 Correct 822 ms 45124 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 35860 KB Output is correct
2 Correct 795 ms 53284 KB Output is correct
3 Correct 967 ms 73708 KB Output is correct
4 Correct 996 ms 74480 KB Output is correct
5 Correct 775 ms 53296 KB Output is correct
6 Correct 821 ms 60252 KB Output is correct
7 Correct 608 ms 49188 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1343 ms 44476 KB Output is correct
3 Correct 893 ms 43780 KB Output is correct
4 Correct 863 ms 44984 KB Output is correct
5 Correct 822 ms 45124 KB Output is correct
6 Correct 784 ms 35860 KB Output is correct
7 Correct 795 ms 53284 KB Output is correct
8 Correct 967 ms 73708 KB Output is correct
9 Correct 996 ms 74480 KB Output is correct
10 Correct 775 ms 53296 KB Output is correct
11 Correct 821 ms 60252 KB Output is correct
12 Correct 608 ms 49188 KB Output is correct
13 Correct 884 ms 54192 KB Output is correct
14 Correct 1006 ms 61240 KB Output is correct
15 Correct 818 ms 53360 KB Output is correct
16 Correct 892 ms 57656 KB Output is correct
17 Correct 851 ms 59696 KB Output is correct
18 Correct 795 ms 53272 KB Output is correct
19 Correct 897 ms 53272 KB Output is correct
20 Correct 811 ms 53260 KB Output is correct
21 Correct 898 ms 54048 KB Output is correct
22 Correct 841 ms 53664 KB Output is correct
23 Correct 848 ms 54112 KB Output is correct
24 Correct 844 ms 60440 KB Output is correct
25 Correct 784 ms 53340 KB Output is correct