Submission #592985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592985	2022-07-10T03:36:37 Z	beaboss	Tracks in the Snow (BOI13_tracks)	C++14	84.6875 / 100	2000 ms	400772 KB

tracks

#include <bits/stdc++.h>

using namespace std;

int main() {
	int h, w;

	cin >> h >> w;

	vector<vector<char> > graph(h, vector<char>(w, 0));

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

	deque<vector<int> > bfs;

	bfs.push_back({0, 0});
	vector<vector<int> > dist(h, vector<int>(w, -1));
	dist[0][0] = 1;
	int ans = 0;
	vector<pair<int, int> > vec = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	while (!bfs.empty()) {
		auto current = bfs.front();
		bfs.pop_front();
		ans = max(ans, dist[current[0]][current[1]]);
		// cout << current[0] << current[1] << dist[current[0]][current[1]] << endl;
		for (pair<int, int> val: vec) {

			if (current[0] + val.first >= 0 &&
				current[0] + val.first < h &&
				current[1] + val.second < w &&
				current[1] + val.second >= 0) {
				if (graph[current[0] + val.first][current[1] + val.second] == '.') continue;
				
				if (graph[current[0] + val.first][current[1] + val.second] == 
					graph[current[0]][current[1]] && dist[current[0] + val.first][current[1] + val.second] == -1) {
					dist[current[0] + val.first][current[1] + val.second] = dist[current[0]][current[1]];
					bfs.push_front({current[0] + val.first, current[1] + val.second});
				} else if (dist[current[0] + val.first][current[1] + val.second] == -1) {
					bfs.push_back({current[0] + val.first, current[1] + val.second});
					dist[current[0] + val.first][current[1] + val.second] = dist[current[0]][current[1]] + 1;
					
				}
			}
		}
	}

	cout << ans << endl;


}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	1840 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	23 ms	2516 KB	Output is correct
5	Correct	7 ms	724 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	7 ms	624 KB	Output is correct
11	Correct	6 ms	912 KB	Output is correct
12	Correct	17 ms	852 KB	Output is correct
13	Correct	9 ms	724 KB	Output is correct
14	Correct	8 ms	740 KB	Output is correct
15	Correct	34 ms	1620 KB	Output is correct
16	Correct	39 ms	1908 KB	Output is correct
17	Correct	24 ms	1492 KB	Output is correct
18	Correct	23 ms	2508 KB	Output is correct

Subtask #2

54.6875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	724 KB	Output is correct
2	Correct	162 ms	8120 KB	Output is correct
3	Correct	1192 ms	78824 KB	Output is correct
4	Correct	281 ms	18736 KB	Output is correct
5	Correct	787 ms	44508 KB	Output is correct
6	Execution timed out	2081 ms	175268 KB	Time limit exceeded
7	Correct	4 ms	772 KB	Output is correct
8	Correct	5 ms	724 KB	Output is correct
9	Correct	6 ms	724 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	4 ms	724 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	158 ms	8136 KB	Output is correct
14	Correct	94 ms	4844 KB	Output is correct
15	Correct	75 ms	5140 KB	Output is correct
16	Correct	69 ms	3628 KB	Output is correct
17	Correct	430 ms	20548 KB	Output is correct
18	Correct	309 ms	20016 KB	Output is correct
19	Correct	281 ms	18724 KB	Output is correct
20	Correct	267 ms	17244 KB	Output is correct
21	Correct	718 ms	46116 KB	Output is correct
22	Correct	772 ms	44528 KB	Output is correct
23	Correct	776 ms	38620 KB	Output is correct
24	Correct	708 ms	45000 KB	Output is correct
25	Correct	1359 ms	78944 KB	Output is correct
26	Execution timed out	2102 ms	400772 KB	Time limit exceeded
27	Execution timed out	2072 ms	252900 KB	Time limit exceeded
28	Execution timed out	2080 ms	175500 KB	Time limit exceeded
29	Execution timed out	2083 ms	158064 KB	Time limit exceeded
30	Execution timed out	2090 ms	203788 KB	Time limit exceeded
31	Correct	1685 ms	53632 KB	Output is correct
32	Execution timed out	2099 ms	242380 KB	Time limit exceeded