oj.uz

Submission #441669

# Submission time Handle Problem Language Result Execution time Memory
441669 2021-07-05T18:19:21 Z maraam Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> ll;

const long long INF = 8020;

const long long MAX_h = 4010;
const long long MAX_w = 4010;

char grid[MAX_h][MAX_w];

long long dist[MAX_h][MAX_w];

long long dr[] = {1, -1, 0, 0};
long long dc[] = {0, 0, 1, -1};

int main() {

	// freopen("tracksinthesnow_in.txt", "r", stdin);

	long long h, w; cin >> h >> w;

	for (long long i = 0; i < h; i++) {
		for (long long j = 0; j < w; j++) {
			cin >> grid[i][j];
		}
	}

	for (long long i = 0; i < h; i++) {
		for (long long j = 0; j < w; j++) {
			dist[i][j] = INF;
		}
	}

	long long ans = 1;

	ll s = ll(0, 0); 

	deque<ll> q; q.push_front(s); dist[s.first][s.second] = 1;

	while (!q.empty()) {

		long long r = q.front().first; long long c = q.front().second; q.pop_front();

		ans = max(ans, dist[r][c]);

		for (long long i = 0; i < 4; i++) {

			long long nr = r + dr[i]; long long nc = c + dc[i];

			if ((nr < 0 || nr >= h || nc < 0 || nc >= w) || grid[nr][nc] == '.') continue;

			if (dist[nr][nc] == INF) {

				if (grid[nr][nc] != grid[r][c]) {
					dist[nr][nc] = dist[r][c] + 1;
					q.push_back(ll(nr, nc));
				}
				if (grid[nr][nc] == grid[r][c]) {
					dist[nr][nc] = dist[r][c];
					q.push_front(ll(nr, nc));
				}

			}

		}

	}

	cout << ans << endl;

	return 0;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6392 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 20 ms 5960 KB Output is correct
5 Correct 8 ms 3244 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 1 ms 680 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 7 ms 2840 KB Output is correct
11 Correct 5 ms 2380 KB Output is correct
12 Correct 10 ms 3404 KB Output is correct
13 Correct 8 ms 3252 KB Output is correct
14 Correct 8 ms 3276 KB Output is correct
15 Correct 25 ms 6536 KB Output is correct
16 Correct 26 ms 6348 KB Output is correct
17 Correct 23 ms 6092 KB Output is correct
18 Correct 16 ms 5936 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31204 KB Output is correct
2 Correct 136 ms 23984 KB Output is correct
3 Execution timed out 2122 ms 563188 KB Time limit exceeded
4 Correct 295 ms 47512 KB Output is correct
5 Correct 659 ms 97616 KB Output is correct
6 Correct 1497 ms 172128 KB Output is correct
7 Correct 18 ms 32588 KB Output is correct
8 Correct 19 ms 31132 KB Output is correct
9 Correct 5 ms 844 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 20 ms 31876 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 135 ms 23988 KB Output is correct
14 Correct 78 ms 15556 KB Output is correct
15 Correct 83 ms 17020 KB Output is correct
16 Correct 56 ms 9052 KB Output is correct
17 Correct 338 ms 51176 KB Output is correct
18 Execution timed out 2078 ms 50596 KB Time limit exceeded
19 Correct 311 ms 47556 KB Output is correct
20 Runtime error 1920 ms 1048576 KB Execution killed with signal 9
21 Correct 672 ms 101712 KB Output is correct
22 Correct 655 ms 98488 KB Output is correct
23 Correct 654 ms 84760 KB Output is correct
24 Correct 660 ms 100188 KB Output is correct
25 Execution timed out 2110 ms 586088 KB Time limit exceeded
26 Correct 1079 ms 228268 KB Output is correct
27 Correct 1390 ms 198672 KB Output is correct
28 Correct 1541 ms 172948 KB Output is correct
29 Correct 1530 ms 169388 KB Output is correct
30 Correct 1440 ms 178572 KB Output is correct
31 Correct 1149 ms 110716 KB Output is correct
32 Correct 1337 ms 176156 KB Output is correct