Submission #1060059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060059		rainboy	Toy (CEOI24_toy)	C11	100 / 100	62 ms	48976 KiB

Main

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

#define N	1500
#define M	1500

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 * M];

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 char cc[N][M + 1];
	static int iiu[N][M], iid[N][M], jjl[N][M], jjr[N][M];
	int n, m, x, y, i, j, is, js, it, jt;

	scanf("%d%d%d%d%*d%d%d%*d", &m, &n, &y, &x, &is, &js);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	it = jt = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '*') {
				it = i, jt = j;
				goto out;
			}
out:
	for (j = 0; j < m; j++) {
		for (i = 0; i < n; i++)
			iiu[i][j] = cc[i][j] == 'X' ? i : (i == 0 ? -1 : iiu[i - 1][j]);
		for (i = n - 1; i >= 0; i--)
			iid[i][j] = cc[i][j] == 'X' ? i : (i + 1 == n ? n : iid[i + 1][j]);
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			jjl[i][j] = cc[i][j] == 'X' ? j : (j == 0 ? -1 : jjl[i][j - 1]);
		for (j = m - 1; j >= 0; j--)
			jjr[i][j] = cc[i][j] == 'X' ? j : (j + 1 == m ? m : jjr[i][j + 1]);
	}
	if (iid[it][jt] - iiu[it][jt] <= x || jjr[it][jt] - jjl[it][jt] <= y) {
		printf("NO\n");
		return 0;
	}
	memset(ds, -1, n * m * sizeof *ds);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (iid[i][j] - iiu[i][j] > x && jjr[i][j] - jjl[i][j] > y) {
				if (i > 0 && cc[i - 1][j] != 'X' && min(jjr[i][j], jjr[i - 1][j]) - max(jjl[i][j], jjl[i - 1][j]) > y)
					join(i * m + j, (i - 1) * m + j);
				if (j > 0 && cc[i][j - 1] != 'X' && min(iid[i][j], iid[i][j - 1]) - max(iiu[i][j], iiu[i][j - 1]) > x)
					join(i * m + j, i * m + (j - 1));
			}
	printf(find(is * m + js) == find(it * m + jt) ? "YES\n" : "NO\n");
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:35:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d%d%d%*d%d%d%*d", &m, &n, &y, &x, &is, &js);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27