Submission #970672

# Submission time Handle Problem Language Result Execution time Memory
970672 2024-04-27T04:13:07 Z ndan Tracks in the Snow (BOI13_tracks) C++14
100 / 100
494 ms 130648 KB
#include <bits/stdc++.h>
using namespace std;

int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

int n, m, depth[4000][4000], ans = 1;
string snow[4000];

bool inside(int x, int y) {
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}

int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> snow[i];

	deque<pair<int, int>> q;
	q.push_back({0, 0});
	depth[0][0] = 1;

	while (q.size()) {
		pair<int, int> c = q.front();
		q.pop_front();
		ans = max(ans, depth[c.first][c.second]);

		for (int i = 0; i < 4; i++) {
			int x = c.first + dx[i], y = c.second + dy[i];
			if (inside(x, y) && depth[x][y] == 0) {
				if (snow[x][y] == snow[c.first][c.second]) {
					depth[x][y] = depth[c.first][c.second];
					q.push_front({x, y});
				} else {
					depth[x][y] = depth[c.first][c.second] + 1;
					q.push_back({x, y});
				}
			}
		}
	}

	cout << ans;
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 9 ms 4016 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 5 ms 3676 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 4 ms 2136 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Correct 3 ms 2140 KB Output is correct
15 Correct 7 ms 3676 KB Output is correct
16 Correct 9 ms 3932 KB Output is correct
17 Correct 6 ms 3676 KB Output is correct
18 Correct 6 ms 3448 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 15964 KB Output is correct
2 Correct 34 ms 11908 KB Output is correct
3 Correct 160 ms 75404 KB Output is correct
4 Correct 56 ms 29508 KB Output is correct
5 Correct 118 ms 51828 KB Output is correct
6 Correct 469 ms 109888 KB Output is correct
7 Correct 8 ms 16732 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 9 ms 16220 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 33 ms 11928 KB Output is correct
14 Correct 17 ms 8120 KB Output is correct
15 Correct 13 ms 10316 KB Output is correct
16 Correct 14 ms 4952 KB Output is correct
17 Correct 73 ms 25172 KB Output is correct
18 Correct 52 ms 32184 KB Output is correct
19 Correct 47 ms 29372 KB Output is correct
20 Correct 37 ms 22464 KB Output is correct
21 Correct 120 ms 50492 KB Output is correct
22 Correct 120 ms 51608 KB Output is correct
23 Correct 163 ms 42172 KB Output is correct
24 Correct 99 ms 47696 KB Output is correct
25 Correct 437 ms 96468 KB Output is correct
26 Correct 256 ms 130648 KB Output is correct
27 Correct 310 ms 123036 KB Output is correct
28 Correct 409 ms 109900 KB Output is correct
29 Correct 494 ms 108356 KB Output is correct
30 Correct 369 ms 112268 KB Output is correct
31 Correct 346 ms 72184 KB Output is correct
32 Correct 281 ms 108236 KB Output is correct