Submission #592979

# Submission time Handle Problem Language Result Execution time Memory
592979 2022-07-10T03:18:37 Z beaboss Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
2000 ms 87024 KB
#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;
	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;
		vector<pair<int, int> > vec = {{0, 1}, {1, 0}};
		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;


}
# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 1492 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 21 ms 1224 KB Output isn't correct
5 Incorrect 6 ms 724 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 5 ms 624 KB Output isn't correct
11 Incorrect 7 ms 596 KB Output isn't correct
12 Incorrect 16 ms 724 KB Output isn't correct
13 Incorrect 7 ms 644 KB Output isn't correct
14 Incorrect 7 ms 724 KB Output isn't correct
15 Incorrect 23 ms 1584 KB Output isn't correct
16 Incorrect 39 ms 1568 KB Output isn't correct
17 Incorrect 22 ms 1492 KB Output isn't correct
18 Incorrect 20 ms 1236 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 724 KB Output isn't correct
2 Incorrect 111 ms 8004 KB Output isn't correct
3 Incorrect 882 ms 78808 KB Output isn't correct
4 Incorrect 242 ms 18724 KB Output isn't correct
5 Incorrect 504 ms 44500 KB Output isn't correct
6 Execution timed out 2079 ms 86932 KB Time limit exceeded
7 Incorrect 5 ms 852 KB Output isn't correct
8 Incorrect 5 ms 724 KB Output isn't correct
9 Incorrect 6 ms 596 KB Output isn't correct
10 Incorrect 3 ms 468 KB Output isn't correct
11 Incorrect 4 ms 852 KB Output isn't correct
12 Incorrect 2 ms 340 KB Output isn't correct
13 Incorrect 112 ms 7992 KB Output isn't correct
14 Incorrect 65 ms 4792 KB Output isn't correct
15 Incorrect 58 ms 5140 KB Output isn't correct
16 Incorrect 51 ms 3480 KB Output isn't correct
17 Incorrect 288 ms 20356 KB Output isn't correct
18 Incorrect 221 ms 20020 KB Output isn't correct
19 Incorrect 264 ms 18736 KB Output isn't correct
20 Incorrect 187 ms 17148 KB Output isn't correct
21 Incorrect 499 ms 46004 KB Output isn't correct
22 Incorrect 501 ms 44504 KB Output isn't correct
23 Incorrect 569 ms 38568 KB Output isn't correct
24 Incorrect 509 ms 44864 KB Output isn't correct
25 Incorrect 911 ms 78824 KB Output isn't correct
26 Correct 1487 ms 60672 KB Output is correct
27 Incorrect 1963 ms 84192 KB Output isn't correct
28 Execution timed out 2082 ms 87024 KB Time limit exceeded
29 Execution timed out 2079 ms 85872 KB Time limit exceeded
30 Execution timed out 2083 ms 86444 KB Time limit exceeded
31 Incorrect 1659 ms 51388 KB Output isn't correct
32 Incorrect 1703 ms 82236 KB Output isn't correct