Submission #999966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999966	2024-06-16T11:40:30 Z	Dipa	Tracks in the Snow (BOI13_tracks)	C++14	80.3125 / 100	2000 ms	97244 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_back({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_back({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_back({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_back({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	153 ms	1972 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	14 ms	1372 KB	Output is correct
5	Correct	8 ms	812 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	4 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	35 ms	860 KB	Output is correct
13	Correct	8 ms	856 KB	Output is correct
14	Correct	8 ms	860 KB	Output is correct
15	Correct	75 ms	1988 KB	Output is correct
16	Correct	153 ms	1976 KB	Output is correct
17	Correct	86 ms	1924 KB	Output is correct
18	Correct	14 ms	1368 KB	Output is correct

Subtask #2

50.3125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	424 ms	9844 KB	Output is correct
3	Execution timed out	2025 ms	96600 KB	Time limit exceeded
4	Correct	1220 ms	22868 KB	Output is correct
5	Correct	117 ms	54256 KB	Output is correct
6	Execution timed out	2033 ms	97244 KB	Time limit exceeded
7	Correct	1 ms	860 KB	Output is correct
8	Correct	2 ms	860 KB	Output is correct
9	Correct	11 ms	832 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	860 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	416 ms	9812 KB	Output is correct
14	Correct	205 ms	5912 KB	Output is correct
15	Correct	10 ms	6236 KB	Output is correct
16	Correct	383 ms	4324 KB	Output is correct
17	Correct	1593 ms	24656 KB	Output is correct
18	Correct	40 ms	24376 KB	Output is correct
19	Correct	1198 ms	22868 KB	Output is correct
20	Execution timed out	2007 ms	20816 KB	Time limit exceeded
21	Execution timed out	2102 ms	56276 KB	Time limit exceeded
22	Correct	104 ms	54228 KB	Output is correct
23	Execution timed out	2025 ms	47188 KB	Time limit exceeded
24	Correct	95 ms	54900 KB	Output is correct
25	Correct	194 ms	96592 KB	Output is correct
26	Correct	237 ms	73952 KB	Output is correct
27	Correct	334 ms	96640 KB	Output is correct
28	Execution timed out	2083 ms	97244 KB	Time limit exceeded
29	Execution timed out	2073 ms	97120 KB	Time limit exceeded
30	Execution timed out	2082 ms	95060 KB	Time limit exceeded
31	Execution timed out	2013 ms	62800 KB	Time limit exceeded
32	Correct	1652 ms	96952 KB	Output is correct