Submission #938051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938051	2024-03-04T18:42:47 Z	TAhmed33	Tracks in the Snow (BOI13_tracks)	C++	19.7917 / 100	633 ms	122464 KB

tracks

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
const int MAXN = 4000;
int n, m;
bool check (int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m;
}
char a[MAXN][MAXN];
int dist[MAXN][MAXN];
deque <pair <int, int>> cur;
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j];
 	cur.push_back({0, 0}); 
 	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dist[i][j] = 1e9;
 	dist[0][0] = 1;
	int ans = 1;
	while (!cur.empty()) {
		auto k = cur.front(); cur.pop_front();
		ans = max(ans, dist[k.first][k.second]);
		for (int i = 0; i < 4; i++) {
			int x = k.first + dx[i], y = k.second + dy[i];
			if (!check(x, y)) continue;
			if (a[x][y] == a[k.first][k.second]) {
				if (dist[k.first][k.second] < dist[x][y]) {
					dist[x][y] = dist[k.first][k.second];
					cur.push_front({x, y});
				}
			} else {
				if (dist[k.first][k.second] + 1 < dist[x][y]) {
					dist[x][y] = dist[k.first][k.second] + 1;
					cur.push_back({x, y});
				}
			}
		}
	}
	cout << ans << '\n';
}

Subtask #1

6.66666666667 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	12892 KB	Output isn't correct
2	Incorrect	1 ms	4444 KB	Output isn't correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Correct	7 ms	13008 KB	Output is correct
5	Incorrect	4 ms	8536 KB	Output isn't correct
6	Incorrect	1 ms	4444 KB	Output isn't correct
7	Incorrect	1 ms	4444 KB	Output isn't correct
8	Correct	1 ms	4444 KB	Output is correct
9	Incorrect	1 ms	4444 KB	Output isn't correct
10	Incorrect	3 ms	6748 KB	Output isn't correct
11	Correct	3 ms	6492 KB	Output is correct
12	Incorrect	6 ms	8540 KB	Output isn't correct
13	Incorrect	4 ms	8540 KB	Output isn't correct
14	Incorrect	5 ms	8540 KB	Output isn't correct
15	Incorrect	13 ms	13148 KB	Output isn't correct
16	Incorrect	15 ms	12892 KB	Output isn't correct
17	Incorrect	12 ms	12756 KB	Output isn't correct
18	Correct	7 ms	12888 KB	Output is correct

Subtask #2

13.125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	21 ms	78428 KB	Output isn't correct
2	Incorrect	57 ms	31088 KB	Output isn't correct
3	Incorrect	476 ms	112656 KB	Output isn't correct
4	Incorrect	130 ms	42576 KB	Output isn't correct
5	Incorrect	251 ms	99280 KB	Output isn't correct
6	Correct	585 ms	92104 KB	Output is correct
7	Incorrect	10 ms	78424 KB	Output isn't correct
8	Incorrect	10 ms	78428 KB	Output isn't correct
9	Incorrect	3 ms	4700 KB	Output isn't correct
10	Incorrect	1 ms	2652 KB	Output isn't correct
11	Incorrect	11 ms	78428 KB	Output isn't correct
12	Incorrect	2 ms	6748 KB	Output isn't correct
13	Incorrect	56 ms	31092 KB	Output isn't correct
14	Incorrect	33 ms	23128 KB	Output isn't correct
15	Incorrect	33 ms	25684 KB	Output isn't correct
16	Incorrect	26 ms	12376 KB	Output isn't correct
17	Incorrect	149 ms	53388 KB	Output isn't correct
18	Incorrect	148 ms	52840 KB	Output isn't correct
19	Incorrect	133 ms	42576 KB	Output isn't correct
20	Incorrect	102 ms	46160 KB	Output isn't correct
21	Incorrect	281 ms	91536 KB	Output isn't correct
22	Incorrect	250 ms	99156 KB	Output isn't correct
23	Incorrect	264 ms	70748 KB	Output isn't correct
24	Incorrect	250 ms	89096 KB	Output isn't correct
25	Incorrect	633 ms	116700 KB	Output isn't correct
26	Correct	446 ms	122464 KB	Output is correct
27	Correct	477 ms	108956 KB	Output is correct
28	Correct	628 ms	92388 KB	Output is correct
29	Correct	573 ms	90320 KB	Output is correct
30	Correct	538 ms	96476 KB	Output is correct
31	Incorrect	531 ms	66720 KB	Output isn't correct
32	Incorrect	498 ms	99840 KB	Output isn't correct