oj.uz

Submission #544608

# Submission time Handle Problem Language Result Execution time Memory
544608 2022-04-02T13:33:22 Z rainboy Tracks in the Snow (BOI13_tracks) C
100 / 100
 754 ms 105000 KB 
#include <stdio.h>

#define N	4000
#define M	4000

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int main() {
	static char cc[N][M + 1];
	static int dd[N][M], qu[N * M * 2];
	int n, m, i, j, d, head, cnt;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			dd[i][j] = n * m + 1;
	head = n * m, cnt = 0;
	dd[0][0] = 1, qu[head + cnt++] = 0 * m + 0;
	while (cnt) {
		int ij, h;

		ij = qu[cnt--, head++], i = ij / m, j = ij % m, d = dd[i][j];
		for (h = 0; h < 4; h++) {
			int i_ = i + di[h], j_ = j + dj[h];

			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] != '.') {
				if (cc[i_][j_] == cc[i][j]) {
					if (dd[i_][j_] > d)
						dd[i_][j_] = d, qu[cnt++, --head] = i_ * m + j_;
				} else {
					if (dd[i_][j_] > d + 1)
						dd[i_][j_] = d + 1, qu[head + cnt++] = i_ * m + j_;
				}
			}
		}
	}
	printf("%d\n", d);
	return 0;
}

Compilation message

tracks.c: In function 'main':
tracks.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
tracks.c:16:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5716 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 676 KB Output is correct
4 Correct 9 ms 5076 KB Output is correct
5 Correct 3 ms 2988 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 2 ms 2004 KB Output is correct
12 Correct 7 ms 3120 KB Output is correct
13 Correct 3 ms 2996 KB Output is correct
14 Correct 3 ms 2992 KB Output is correct
15 Correct 13 ms 5824 KB Output is correct
16 Correct 15 ms 5768 KB Output is correct
17 Correct 10 ms 5460 KB Output is correct
18 Correct 9 ms 5032 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30648 KB Output is correct
2 Correct 47 ms 19032 KB Output is correct
3 Correct 263 ms 101840 KB Output is correct
4 Correct 82 ms 34532 KB Output is correct
5 Correct 171 ms 85372 KB Output is correct
6 Correct 751 ms 105000 KB Output is correct
7 Correct 13 ms 32044 KB Output is correct
8 Correct 13 ms 30676 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 12 ms 31424 KB Output is correct
12 Correct 1 ms 1584 KB Output is correct
13 Correct 48 ms 19092 KB Output is correct
14 Correct 30 ms 12656 KB Output is correct
15 Correct 24 ms 13516 KB Output is correct
16 Correct 25 ms 7220 KB Output is correct
17 Correct 120 ms 39372 KB Output is correct
18 Correct 71 ms 37732 KB Output is correct
19 Correct 66 ms 34584 KB Output is correct
20 Correct 76 ms 32652 KB Output is correct
21 Correct 158 ms 74516 KB Output is correct
22 Correct 178 ms 85332 KB Output is correct
23 Correct 267 ms 63084 KB Output is correct
24 Correct 144 ms 75244 KB Output is correct
25 Correct 362 ms 103260 KB Output is correct
26 Correct 431 ms 104744 KB Output is correct
27 Correct 579 ms 103056 KB Output is correct
28 Correct 754 ms 104924 KB Output is correct
29 Correct 739 ms 104752 KB Output is correct
30 Correct 655 ms 102300 KB Output is correct
31 Correct 698 ms 92948 KB Output is correct
32 Correct 494 ms 101988 KB Output is correct