Submission #479392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479392	2021-10-11T15:06:54 Z	rainboy	Konj (COCI19_konj)	C	70 / 70	71 ms	1428 KB

konj

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

#define N	300
#define M	300

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ds[(N + 1) * (M + 1)];

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

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

int main() {
	static int aa[N + 1][M + 1], bb[M + 1][N + 1];
	static char cc[N + 1][M + 2];
	int k, i, j, i1, j1, i2, j2, r;

	scanf("%d", &k);
	while (k--) {
		scanf("%d%d%d%d", &j1, &i1, &j2, &i2), i1 = N - i1, i2 = N - i2;
		if (j1 < j2)
			aa[i1][j1]++, aa[i1][j2]--;
		else if (j1 > j2)
			aa[i1][j2]++, aa[i1][j1]--;
		else if (i1 < i2)
			bb[j1][i1]++, bb[j1][i2]--;
		else if (i1 > i2)
			bb[j1][i2]++, bb[j1][i1]--;
	}
	memset(ds, -1, (N + 1) * (M + 1) * sizeof *ds);
	for (i = 0; i <= N; i++) {
		for (j = 1; j <= M; j++)
			aa[i][j] += aa[i][j - 1];
		for (j = 0; j < M; j++)
			if (aa[i][j])
				join(i * (M + 1) + j, i * (M + 1) + (j + 1));
	}
	for (j = 0; j <= M; j++) {
		for (i = 1; i <= N; i++)
			bb[j][i] += bb[j][i - 1];
		for (i = 0; i < N; i++)
			if (bb[j][i])
				join(i * (M + 1) + j, (i + 1) * (M + 1) + j);
	}
	scanf("%d%d", &j, &i), i = N - i, r = find(i * (M + 1) + j);
	i1 = i, j1 = j, i2 = i, j2 = j;
	for (i = 0; i <= N; i++)
		for (j = 0; j <= M; j++)
			if ((cc[i][j] = find(i * (M + 1) + j) == r ? '#' : '.') == '#')
				i1 = min(i1, i), i2 = max(i2, i), j1 = min(j1, j), j2 = max(j2, j);
	for (i = i1; i <= i2; i++) {
		cc[i][j2 + 1] = 0;
		printf("%s\n", cc[i] + j1);
	}
	return 0;
}

Compilation message

konj.c: In function 'main':
konj.c:35:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d", &k);
      |  ^~~~~~~~~~~~~~~
konj.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d%d%d", &j1, &i1, &j2, &i2), i1 = N - i1, i2 = N - i2;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
konj.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d", &j, &i), i = N - i, r = find(i * (M + 1) + j);
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1356 KB	Output is correct
2	Correct	2 ms	1356 KB	Output is correct
3	Correct	71 ms	1428 KB	Output is correct
4	Correct	2 ms	1356 KB	Output is correct
5	Correct	2 ms	1356 KB	Output is correct
6	Correct	2 ms	1356 KB	Output is correct
7	Correct	2 ms	1356 KB	Output is correct
8	Correct	2 ms	1356 KB	Output is correct
9	Correct	2 ms	1356 KB	Output is correct
10	Correct	3 ms	1356 KB	Output is correct