oj.uz

Submission #959038

# Submission time Handle Problem Language Result Execution time Memory
959038 2024-04-07T12:11:25 Z DaoMinh Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 459 ms 131124 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;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3928 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 6 ms 3416 KB Output is correct
5 Correct 3 ms 2140 KB Output is correct
6 Correct 0 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 1112 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1548 KB Output is correct
12 Correct 4 ms 2136 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Correct 2 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 7 ms 3676 KB Output is correct
18 Correct 5 ms 3416 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15960 KB Output is correct
2 Correct 28 ms 11856 KB Output is correct
3 Correct 156 ms 75436 KB Output is correct
4 Correct 49 ms 29432 KB Output is correct
5 Correct 123 ms 51624 KB Output is correct
6 Correct 459 ms 109972 KB Output is correct
7 Correct 7 ms 16728 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 8 ms 16220 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 28 ms 11884 KB Output is correct
14 Correct 16 ms 8280 KB Output is correct
15 Correct 14 ms 10328 KB Output is correct
16 Correct 14 ms 4956 KB Output is correct
17 Correct 70 ms 25228 KB Output is correct
18 Correct 57 ms 32220 KB Output is correct
19 Correct 46 ms 29460 KB Output is correct
20 Correct 46 ms 22368 KB Output is correct
21 Correct 92 ms 50444 KB Output is correct
22 Correct 116 ms 51628 KB Output is correct
23 Correct 155 ms 42176 KB Output is correct
24 Correct 93 ms 47656 KB Output is correct
25 Correct 311 ms 96412 KB Output is correct
26 Correct 253 ms 131124 KB Output is correct
27 Correct 336 ms 123084 KB Output is correct
28 Correct 414 ms 110208 KB Output is correct
29 Correct 454 ms 108560 KB Output is correct
30 Correct 368 ms 112344 KB Output is correct
31 Correct 350 ms 72668 KB Output is correct
32 Correct 285 ms 108356 KB Output is correct