Submission #999969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999969	2024-06-16T11:42:17 Z	Dipa	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	502 ms	128844 KB

tracks

#include <bits/stdc++.h>
#define INF_INT 2147483647
#define what_is(x) cerr << #x << " is " << x << endl;
#define all(v) v.begin(), v.end()
typedef long long ll;
using namespace std;

void solve() {
	int H, W; cin >> H >> W;

	string grid[H];
	for (auto &el: grid) cin >> el;

	vector<vector<int>> dist(H, vector<int>(W, 1e9));
	deque<pair<int, int>> dq;
	dq.push_back({0, 0});
	dist[0][0] = 0;

	while (!dq.empty()) {
		pair<int, int> current = dq.front();
		dq.pop_front();

		// go down
		if (current.first + 1 < H && (grid[current.first + 1][current.second] != '.')) {
			if (grid[current.first + 1][current.second] != grid[current.first][current.second]) {
				if (dist[current.first + 1][current.second] > dist[current.first][current.second] + 1) {
					dist[current.first + 1][current.second] = dist[current.first][current.second] + 1;
					dq.push_back({current.first + 1, current.second});
				}
			} else {
				if (dist[current.first + 1][current.second] > dist[current.first][current.second]) {
					dist[current.first + 1][current.second] = dist[current.first][current.second];
					dq.push_front({current.first + 1, current.second});
				}
			}
		}

		// go left
		// cout << "UP" << endl;

		if (current.second - 1 >= 0 && grid[current.first][current.second - 1] != '.') {

			if (grid[current.first][current.second - 1] != grid[current.first][current.second]) {
				if (dist[current.first][current.second - 1] > dist[current.first][current.second] + 1) {
					dist[current.first][current.second - 1] = dist[current.first][current.second] + 1;
					dq.push_back({current.first, current.second - 1});
				}
			} else {
				if (dist[current.first][current.second - 1] > dist[current.first][current.second]) {
					dist[current.first][current.second - 1] = dist[current.first][current.second];
					dq.push_front({current.first, current.second - 1});
				}
			}
		}

		// go right
		if (current.second + 1 < W && grid[current.first][current.second + 1] != '.') {

			if (grid[current.first][current.second + 1] != grid[current.first][current.second]) {
				if (dist[current.first][current.second + 1] > dist[current.first][current.second] + 1) {
					dist[current.first][current.second + 1] = dist[current.first][current.second] + 1;
					dq.push_back({current.first, current.second + 1});
				}
			} else {
				if (dist[current.first][current.second + 1] > dist[current.first][current.second]) {
					dist[current.first][current.second + 1] = dist[current.first][current.second];
					dq.push_front({current.first, current.second + 1});
				}
			}
		}

		// go up
		if (current.first - 1 >= 0 && grid[current.first - 1][current.second] != '.') {

			if (grid[current.first - 1][current.second] != grid[current.first][current.second]) {
				if (dist[current.first - 1][current.second] > dist[current.first][current.second] + 1) {
					dist[current.first - 1][current.second] = dist[current.first][current.second] + 1;
					dq.push_back({current.first - 1, current.second});
				}
			} else {
				if (dist[current.first - 1][current.second] > dist[current.first][current.second]) {
					dist[current.first - 1][current.second] = dist[current.first][current.second];
					dq.push_front({current.first - 1, current.second});
				}
			}
		}
	}

	int ans = -1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (dist[i][j] != (int) 1e9) ans = max(ans, dist[i][j]);
		}
	}

	cout << ans + 1 << '\n';
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1884 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	4 ms	1520 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	2 ms	524 KB	Output is correct
12	Correct	5 ms	860 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	2 ms	860 KB	Output is correct
15	Correct	7 ms	1880 KB	Output is correct
16	Correct	10 ms	1884 KB	Output is correct
17	Correct	6 ms	1912 KB	Output is correct
18	Correct	4 ms	1372 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	856 KB	Output is correct
2	Correct	28 ms	9132 KB	Output is correct
3	Correct	169 ms	89220 KB	Output is correct
4	Correct	47 ms	21488 KB	Output is correct
5	Correct	108 ms	50276 KB	Output is correct
6	Correct	502 ms	103560 KB	Output is correct
7	Correct	2 ms	876 KB	Output is correct
8	Correct	2 ms	860 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	724 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	27 ms	9308 KB	Output is correct
14	Correct	15 ms	5724 KB	Output is correct
15	Correct	10 ms	6236 KB	Output is correct
16	Correct	13 ms	4200 KB	Output is correct
17	Correct	70 ms	22868 KB	Output is correct
18	Correct	39 ms	22612 KB	Output is correct
19	Correct	44 ms	21044 KB	Output is correct
20	Correct	36 ms	19548 KB	Output is correct
21	Correct	91 ms	51944 KB	Output is correct
22	Correct	106 ms	50004 KB	Output is correct
23	Correct	142 ms	43348 KB	Output is correct
24	Correct	92 ms	50524 KB	Output is correct
25	Correct	196 ms	89028 KB	Output is correct
26	Correct	249 ms	118300 KB	Output is correct
27	Correct	362 ms	128844 KB	Output is correct
28	Correct	484 ms	103768 KB	Output is correct
29	Correct	462 ms	101372 KB	Output is correct
30	Correct	427 ms	107376 KB	Output is correct
31	Correct	379 ms	57432 KB	Output is correct
32	Correct	327 ms	111456 KB	Output is correct