Submission #575756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
575756	2022-06-11T08:51:06 Z	acatmeowmeow	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	920 ms	272248 KB

tracks

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 4e3 + 5;
int n, m, d[N][N], rab = 0, fox = 0;
char grid[N][N];
vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
deque<pair<int, pair<int, int>>> dq;

bool inbound(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m && grid[x][y] != '.';
}

void bfs() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			d[i][j] = 1e18;
		}
	}
	dq.push_front({1, {1, 1}});
	d[1][1] = 1;
	while (dq.size()) {
		int p = dq.front().first, x = dq.front().second.first, y = dq.front().second.second; dq.pop_front();
		if (p != d[x][y]) continue;
		for (int k = 0; k < 4; k++) {
			int tox = x + dx[k], toy = y + dy[k];
			if (!inbound(tox, toy)) continue;
			int c = grid[x][y] != grid[tox][toy];
			if (d[tox][toy] <= d[x][y] + c) continue;
			d[tox][toy] = d[x][y] + c;
			if (c) dq.push_back({d[tox][toy], {tox, toy}});
			else dq.push_front({d[tox][toy], {tox, toy}});
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (d[i][j] != 1e18) ans = max(ans, d[i][j]);
		}
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 'R') rab = 1;
			if (grid[i][j] == 'F') fox = 1;
		}
	}
	bfs();
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	6540 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	1 ms	724 KB	Output is correct
4	Correct	12 ms	6232 KB	Output is correct
5	Correct	4 ms	3284 KB	Output is correct
6	Correct	1 ms	452 KB	Output is correct
7	Correct	1 ms	820 KB	Output is correct
8	Correct	1 ms	840 KB	Output is correct
9	Correct	1 ms	1236 KB	Output is correct
10	Correct	4 ms	2824 KB	Output is correct
11	Correct	3 ms	2388 KB	Output is correct
12	Correct	7 ms	3412 KB	Output is correct
13	Correct	4 ms	3284 KB	Output is correct
14	Correct	4 ms	3284 KB	Output is correct
15	Correct	16 ms	6484 KB	Output is correct
16	Correct	17 ms	6484 KB	Output is correct
17	Correct	13 ms	6276 KB	Output is correct
18	Correct	10 ms	6228 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	31188 KB	Output is correct
2	Correct	63 ms	22792 KB	Output is correct
3	Correct	413 ms	142036 KB	Output is correct
4	Correct	118 ms	44852 KB	Output is correct
5	Correct	247 ms	95132 KB	Output is correct
6	Correct	910 ms	185080 KB	Output is correct
7	Correct	15 ms	32596 KB	Output is correct
8	Correct	14 ms	31120 KB	Output is correct
9	Correct	3 ms	924 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	15 ms	32024 KB	Output is correct
12	Correct	1 ms	1620 KB	Output is correct
13	Correct	67 ms	22604 KB	Output is correct
14	Correct	37 ms	14788 KB	Output is correct
15	Correct	41 ms	16120 KB	Output is correct
16	Correct	28 ms	8660 KB	Output is correct
17	Correct	154 ms	48260 KB	Output is correct
18	Correct	147 ms	47640 KB	Output is correct
19	Correct	121 ms	44772 KB	Output is correct
20	Correct	99 ms	41220 KB	Output is correct
21	Correct	250 ms	97956 KB	Output is correct
22	Correct	238 ms	94804 KB	Output is correct
23	Correct	302 ms	81128 KB	Output is correct
24	Correct	256 ms	96468 KB	Output is correct
25	Correct	699 ms	141548 KB	Output is correct
26	Correct	601 ms	272248 KB	Output is correct
27	Correct	807 ms	228200 KB	Output is correct
28	Correct	920 ms	184536 KB	Output is correct
29	Correct	910 ms	172968 KB	Output is correct
30	Correct	890 ms	197712 KB	Output is correct
31	Correct	677 ms	107156 KB	Output is correct
32	Correct	728 ms	199452 KB	Output is correct