oj.uz

답안 #592986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592986 2022-07-10T03:39:10 Z beaboss Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 401044 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;
	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] == '.' || dist[current[0] + val.first][current[1] + val.second] != -1) 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] = dist[current[0]][current[1]];
					bfs.push_front({current[0] + val.first, current[1] + val.second});
				} else {
					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

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2104 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 25 ms 2748 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 7 ms 980 KB Output is correct
12 Correct 16 ms 992 KB Output is correct
13 Correct 7 ms 824 KB Output is correct
14 Correct 7 ms 820 KB Output is correct
15 Correct 36 ms 1832 KB Output is correct
16 Correct 37 ms 2092 KB Output is correct
17 Correct 25 ms 1620 KB Output is correct
18 Correct 23 ms 2628 KB Output is correct

Subtask #2
54.6875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 824 KB Output is correct
2 Correct 146 ms 8276 KB Output is correct
3 Correct 1199 ms 79180 KB Output is correct
4 Correct 277 ms 18980 KB Output is correct
5 Correct 758 ms 44788 KB Output is correct
6 Execution timed out 2071 ms 175572 KB Time limit exceeded
7 Correct 5 ms 852 KB Output is correct
8 Correct 6 ms 852 KB Output is correct
9 Correct 7 ms 692 KB Output is correct
10 Correct 3 ms 440 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 143 ms 8380 KB Output is correct
14 Correct 86 ms 4976 KB Output is correct
15 Correct 86 ms 5364 KB Output is correct
16 Correct 69 ms 3652 KB Output is correct
17 Correct 369 ms 20700 KB Output is correct
18 Correct 328 ms 20232 KB Output is correct
19 Correct 268 ms 19080 KB Output is correct
20 Correct 279 ms 17404 KB Output is correct
21 Correct 740 ms 46388 KB Output is correct
22 Correct 754 ms 44764 KB Output is correct
23 Correct 802 ms 38876 KB Output is correct
24 Correct 683 ms 45116 KB Output is correct
25 Correct 1353 ms 79192 KB Output is correct
26 Execution timed out 2077 ms 401044 KB Time limit exceeded
27 Execution timed out 2101 ms 252940 KB Time limit exceeded
28 Execution timed out 2086 ms 175692 KB Time limit exceeded
29 Execution timed out 2091 ms 158000 KB Time limit exceeded
30 Execution timed out 2087 ms 203520 KB Time limit exceeded
31 Correct 1573 ms 53760 KB Output is correct
32 Execution timed out 2059 ms 242388 KB Time limit exceeded