답안 #592976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592976	2022-07-10T03:15:04 Z	beaboss	Tracks in the Snow (BOI13_tracks)	C++14	2.1875 / 100	2000 ms	99928 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] = 0;
	int ans = 0;
	while (!bfs.empty()) {
		auto current = bfs.front();
		bfs.pop_front();
		if (graph[current[0]][current[1]] == '.') continue;
		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] == 
					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;


}

Subtask #1

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	39 ms	1748 KB	Output isn't correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Incorrect	1 ms	300 KB	Output isn't correct
4	Execution timed out	2064 ms	1336 KB	Time limit exceeded
5	Incorrect	7 ms	728 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	2077 ms	324 KB	Time limit exceeded
9	Incorrect	1 ms	340 KB	Output isn't correct
10	Incorrect	6 ms	692 KB	Output isn't correct
11	Execution timed out	2073 ms	600 KB	Time limit exceeded
12	Incorrect	14 ms	824 KB	Output isn't correct
13	Incorrect	7 ms	820 KB	Output isn't correct
14	Incorrect	7 ms	804 KB	Output isn't correct
15	Incorrect	26 ms	1832 KB	Output isn't correct
16	Incorrect	43 ms	1852 KB	Output isn't correct
17	Incorrect	25 ms	1668 KB	Output isn't correct
18	Execution timed out	2089 ms	1364 KB	Time limit exceeded

Subtask #2

2.1875 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	980 KB	Output isn't correct
2	Incorrect	130 ms	9636 KB	Output isn't correct
3	Incorrect	900 ms	94672 KB	Output isn't correct
4	Incorrect	269 ms	22556 KB	Output isn't correct
5	Incorrect	513 ms	53460 KB	Output isn't correct
6	Execution timed out	2091 ms	95952 KB	Time limit exceeded
7	Incorrect	4 ms	852 KB	Output isn't correct
8	Incorrect	5 ms	1076 KB	Output isn't correct
9	Incorrect	7 ms	852 KB	Output isn't correct
10	Incorrect	3 ms	596 KB	Output isn't correct
11	Incorrect	4 ms	1108 KB	Output isn't correct
12	Incorrect	2 ms	440 KB	Output isn't correct
13	Incorrect	143 ms	9644 KB	Output isn't correct
14	Incorrect	76 ms	5660 KB	Output isn't correct
15	Incorrect	57 ms	6256 KB	Output isn't correct
16	Incorrect	54 ms	4112 KB	Output isn't correct
17	Incorrect	335 ms	24496 KB	Output isn't correct
18	Incorrect	220 ms	23972 KB	Output isn't correct
19	Incorrect	285 ms	22552 KB	Output isn't correct
20	Incorrect	208 ms	20628 KB	Output isn't correct
21	Incorrect	519 ms	55360 KB	Output isn't correct
22	Incorrect	496 ms	53452 KB	Output isn't correct
23	Incorrect	642 ms	46300 KB	Output isn't correct
24	Incorrect	521 ms	53932 KB	Output isn't correct
25	Incorrect	911 ms	94664 KB	Output isn't correct
26	Correct	1536 ms	72664 KB	Output is correct
27	Execution timed out	2069 ms	99928 KB	Time limit exceeded
28	Execution timed out	2023 ms	95944 KB	Time limit exceeded
29	Execution timed out	2085 ms	98124 KB	Time limit exceeded
30	Execution timed out	2056 ms	94092 KB	Time limit exceeded
31	Incorrect	1752 ms	61616 KB	Output isn't correct
32	Execution timed out	2075 ms	94916 KB	Time limit exceeded