oj.uz

Submission #938048

# Submission time Handle Problem Language Result Execution time Memory
938048 2024-03-04T18:40:26 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
0 / 100
 639 ms 148728 KB 
#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];
bool vis[MAXN][MAXN]; 
int dist[MAXN][MAXN];
deque <pair <int, int>> cur;
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	memset(vis, false, sizeof(vis));
	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}); vis[0][0] = 1;
 	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = 1e9;
 	dist[0][0] = 0;
	int ans = 0;
	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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 27384 KB Output isn't correct
2 Incorrect 3 ms 20828 KB Output isn't correct
3 Incorrect 3 ms 20828 KB Output isn't correct
4 Incorrect 10 ms 27228 KB Output isn't correct
5 Incorrect 6 ms 25180 KB Output isn't correct
6 Incorrect 3 ms 20824 KB Output isn't correct
7 Incorrect 3 ms 20828 KB Output isn't correct
8 Incorrect 3 ms 20828 KB Output isn't correct
9 Incorrect 3 ms 20828 KB Output isn't correct
10 Incorrect 5 ms 23128 KB Output isn't correct
11 Incorrect 4 ms 23132 KB Output isn't correct
12 Incorrect 7 ms 25180 KB Output isn't correct
13 Incorrect 7 ms 25180 KB Output isn't correct
14 Incorrect 6 ms 25180 KB Output isn't correct
15 Incorrect 15 ms 29664 KB Output isn't correct
16 Incorrect 15 ms 27224 KB Output isn't correct
17 Incorrect 15 ms 27228 KB Output isn't correct
18 Incorrect 11 ms 27412 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 93524 KB Output isn't correct
2 Incorrect 68 ms 47628 KB Output isn't correct
3 Incorrect 481 ms 128224 KB Output isn't correct
4 Incorrect 128 ms 56912 KB Output isn't correct
5 Incorrect 261 ms 113492 KB Output isn't correct
6 Incorrect 606 ms 108176 KB Output isn't correct
7 Incorrect 19 ms 94300 KB Output isn't correct
8 Incorrect 17 ms 93532 KB Output isn't correct
9 Incorrect 3 ms 20828 KB Output isn't correct
10 Incorrect 3 ms 18780 KB Output isn't correct
11 Incorrect 17 ms 94084 KB Output isn't correct
12 Incorrect 4 ms 23132 KB Output isn't correct
13 Incorrect 59 ms 47388 KB Output isn't correct
14 Incorrect 33 ms 37164 KB Output isn't correct
15 Incorrect 37 ms 40028 KB Output isn't correct
16 Incorrect 13 ms 25432 KB Output isn't correct
17 Incorrect 141 ms 67808 KB Output isn't correct
18 Incorrect 151 ms 67212 KB Output isn't correct
19 Incorrect 127 ms 56632 KB Output isn't correct
20 Incorrect 98 ms 57940 KB Output isn't correct
21 Incorrect 280 ms 105544 KB Output isn't correct
22 Incorrect 250 ms 113492 KB Output isn't correct
23 Incorrect 246 ms 79328 KB Output isn't correct
24 Incorrect 253 ms 105384 KB Output isn't correct
25 Incorrect 639 ms 132604 KB Output isn't correct
26 Incorrect 464 ms 148728 KB Output isn't correct
27 Incorrect 457 ms 124316 KB Output isn't correct
28 Incorrect 594 ms 107964 KB Output isn't correct
29 Incorrect 582 ms 105988 KB Output isn't correct
30 Incorrect 535 ms 111976 KB Output isn't correct
31 Incorrect 532 ms 83124 KB Output isn't correct
32 Incorrect 517 ms 115680 KB Output isn't correct