Submission #333971

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333971	2020-12-08T04:13:07 Z	codemaster111	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	954 ms	130812 KB

tracks

#include <bits/stdc++.h>
using namespace std;

const int MX = 4001;
int n, m, d[MX][MX], dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
string g[MX];

bool inside(int r, int c) {
	return (r >= 0 && r < n && c >= 0 && c < m && g[r][c] != '.');
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> g[i];

	int ans = 1;
	d[0][0] = 1;
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	while (!q.empty()) {
		pair<int, int> v = q.front(); q.pop_front();
		ans = max(ans, d[v.first][v.second]);
		for (int i = 0; i < 4; ++i) {
			int x = v.first+dx[i], y = v.second+dy[i];
			if (inside(x, y) && d[x][y] == 0) {
				if (g[x][y] == g[v.first][v.second]) {
					d[x][y] = d[v.first][v.second];
					q.push_front({x, y});
				} else {
					d[x][y] = d[v.first][v.second]+1;
					q.push_back({x, y});
				}
			}
		}
	}
	cout << ans << '\n';
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	3948 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	620 KB	Output is correct
4	Correct	10 ms	3564 KB	Output is correct
5	Correct	3 ms	2028 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	768 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	3 ms	1772 KB	Output is correct
11	Correct	3 ms	1516 KB	Output is correct
12	Correct	6 ms	2156 KB	Output is correct
13	Correct	3 ms	2028 KB	Output is correct
14	Correct	3 ms	2028 KB	Output is correct
15	Correct	11 ms	3820 KB	Output is correct
16	Correct	21 ms	3948 KB	Output is correct
17	Correct	9 ms	3692 KB	Output is correct
18	Correct	9 ms	3564 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	15980 KB	Output is correct
2	Correct	62 ms	12012 KB	Output is correct
3	Correct	259 ms	75244 KB	Output is correct
4	Correct	82 ms	29420 KB	Output is correct
5	Correct	167 ms	51564 KB	Output is correct
6	Correct	863 ms	110936 KB	Output is correct
7	Correct	14 ms	16876 KB	Output is correct
8	Correct	17 ms	15980 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	1 ms	620 KB	Output is correct
11	Correct	13 ms	16364 KB	Output is correct
12	Correct	2 ms	1280 KB	Output is correct
13	Correct	47 ms	12012 KB	Output is correct
14	Correct	27 ms	7916 KB	Output is correct
15	Correct	32 ms	10348 KB	Output is correct
16	Correct	21 ms	4972 KB	Output is correct
17	Correct	126 ms	25324 KB	Output is correct
18	Correct	93 ms	32236 KB	Output is correct
19	Correct	75 ms	29420 KB	Output is correct
20	Correct	60 ms	22636 KB	Output is correct
21	Correct	144 ms	50796 KB	Output is correct
22	Correct	161 ms	51436 KB	Output is correct
23	Correct	242 ms	42304 KB	Output is correct
24	Correct	147 ms	47468 KB	Output is correct
25	Correct	477 ms	96492 KB	Output is correct
26	Correct	954 ms	130812 KB	Output is correct
27	Correct	802 ms	124188 KB	Output is correct
28	Correct	832 ms	110808 KB	Output is correct
29	Correct	809 ms	109008 KB	Output is correct
30	Correct	824 ms	114196 KB	Output is correct
31	Correct	632 ms	72172 KB	Output is correct
32	Correct	866 ms	116112 KB	Output is correct