oj.uz

Submission #1060054

# Submission time Handle Problem Language Result Execution time Memory
1060054 2024-08-15T10:18:52 Z rainboy Toy (CEOI24_toy) C
9 / 100
 5 ms 17516 KB 
#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, &x, &y, &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

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, &x, &y, &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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 1 ms 10588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 1 ms 10588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17500 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 3 ms 17500 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 4 ms 17500 KB Output is correct
11 Correct 4 ms 17332 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct
13 Correct 4 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 4 ms 17340 KB Output is correct
16 Correct 3 ms 17408 KB Output is correct
17 Correct 3 ms 17332 KB Output is correct
18 Correct 4 ms 17428 KB Output is correct
19 Correct 3 ms 17500 KB Output is correct
20 Correct 3 ms 17500 KB Output is correct
21 Correct 3 ms 17516 KB Output is correct
22 Correct 3 ms 17332 KB Output is correct
23 Correct 3 ms 17336 KB Output is correct
24 Correct 4 ms 17500 KB Output is correct
25 Correct 4 ms 17500 KB Output is correct
26 Correct 3 ms 17500 KB Output is correct
27 Correct 4 ms 17500 KB Output is correct
28 Correct 3 ms 17500 KB Output is correct
29 Correct 4 ms 17416 KB Output is correct
30 Correct 4 ms 17244 KB Output is correct
31 Correct 2 ms 16988 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 2 ms 16988 KB Output is correct
34 Correct 4 ms 17244 KB Output is correct
35 Correct 3 ms 17244 KB Output is correct
36 Correct 3 ms 17244 KB Output is correct
37 Correct 4 ms 17244 KB Output is correct
38 Correct 3 ms 17244 KB Output is correct
39 Correct 3 ms 17408 KB Output is correct
40 Correct 3 ms 17448 KB Output is correct
41 Correct 3 ms 17244 KB Output is correct
42 Correct 3 ms 17500 KB Output is correct
43 Correct 3 ms 17500 KB Output is correct
44 Correct 5 ms 17416 KB Output is correct
45 Correct 3 ms 17500 KB Output is correct
46 Correct 2 ms 17244 KB Output is correct

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 1 ms 10588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 1 ms 10588 KB Output isn't correct
4 Halted 0 ms 0 KB -