Submission #592978

# Submission time Handle Problem Language Result Execution time Memory
592978 2022-07-10T03:16:50 Z beaboss Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
2000 ms 85132 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] = 0;
	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 + 1 << endl;


}
# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 1852 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 Execution timed out 2075 ms 1248 KB Time limit exceeded
5 Incorrect 7 ms 724 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Execution timed out 2098 ms 340 KB Time limit exceeded
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 5 ms 684 KB Output isn't correct
11 Execution timed out 2079 ms 608 KB Time limit exceeded
12 Incorrect 15 ms 884 KB Output isn't correct
13 Incorrect 7 ms 724 KB Output isn't correct
14 Incorrect 6 ms 724 KB Output isn't correct
15 Incorrect 27 ms 1864 KB Output isn't correct
16 Incorrect 40 ms 1944 KB Output isn't correct
17 Incorrect 25 ms 1676 KB Output isn't correct
18 Execution timed out 2071 ms 1364 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 820 KB Output isn't correct
2 Incorrect 113 ms 8860 KB Output isn't correct
3 Incorrect 868 ms 79832 KB Output isn't correct
4 Incorrect 251 ms 19700 KB Output isn't correct
5 Incorrect 482 ms 45484 KB Output isn't correct
6 Execution timed out 2070 ms 81356 KB Time limit exceeded
7 Incorrect 4 ms 852 KB Output isn't correct
8 Incorrect 5 ms 852 KB Output isn't correct
9 Incorrect 6 ms 732 KB Output isn't correct
10 Incorrect 3 ms 444 KB Output isn't correct
11 Incorrect 5 ms 832 KB Output isn't correct
12 Incorrect 2 ms 340 KB Output isn't correct
13 Incorrect 115 ms 8960 KB Output isn't correct
14 Incorrect 64 ms 5656 KB Output isn't correct
15 Incorrect 56 ms 6084 KB Output isn't correct
16 Incorrect 50 ms 4112 KB Output isn't correct
17 Incorrect 292 ms 21224 KB Output isn't correct
18 Incorrect 223 ms 20780 KB Output isn't correct
19 Incorrect 240 ms 19624 KB Output isn't correct
20 Incorrect 190 ms 18020 KB Output isn't correct
21 Incorrect 504 ms 46936 KB Output isn't correct
22 Incorrect 497 ms 45388 KB Output isn't correct
23 Incorrect 557 ms 39408 KB Output isn't correct
24 Incorrect 499 ms 45756 KB Output isn't correct
25 Incorrect 882 ms 79848 KB Output isn't correct
26 Correct 1480 ms 61696 KB Output is correct
27 Execution timed out 2081 ms 85132 KB Time limit exceeded
28 Execution timed out 2078 ms 81104 KB Time limit exceeded
29 Execution timed out 2095 ms 82392 KB Time limit exceeded
30 Execution timed out 2090 ms 78888 KB Time limit exceeded
31 Incorrect 1776 ms 51524 KB Output isn't correct
32 Execution timed out 2078 ms 79200 KB Time limit exceeded