oj.uz

답안 #938051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938051 2024-03-04T18:42:47 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
19.7917 / 100
 633 ms 122464 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];
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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