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

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;
	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;


}

Subtask #1

0 / 30.0

#	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

Subtask #2

2.1875 / 70.0

#	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