oj.uz

답안 #1095573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095573 2024-10-02T15:04:04 Z mat_jur Tracks in the Snow (BOI13_tracks) C++17
1.66667 / 100
 1122 ms 179364 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int inf = 1e9;

int bfs(vector<vector<char>> c, char z) {
	int n = ssize(c), m = ssize(c[0]);
	
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < m; ++j)
			if (c[i][j] != z)
				c[i][j] = '.';

	int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

	vector<vector<int>> dist {
		n,
		vector<int>(m, inf)
	};
	deque<pair<int, int>> q;
	q.push_back({0, 0});
	dist[0][0] = 0;

	while (ssize(q)) {
		auto [x, y] = q.front();
		q.pop_front();

		for (int i = 0; i < 4; ++i) {
			if (!(x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y+dy[i] < m) || dist[x+dx[i]][y+dy[i]] != inf) continue;
			if (c[x][y] != c[x+dx[i]][y+dy[i]]) {
				dist[x+dx[i]][y+dy[i]] = dist[x][y] + 1;
				q.push_back({x+dx[i], y+dy[i]});
			}
			else {
				dist[x+dx[i]][y+dy[i]] = dist[x][y];
				q.push_front({x+dx[i], y+dy[i]});
			}
		}
	}

	int mx = -inf;
	for (int i = 1; i < n-1; ++i)
		for (int j = 1; j < m-1; ++j) 
			if (c[i][j] == z)
				mx = max(mx, dist[i][j]);

	return mx;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int h, w;
	cin >> h >> w;
	vector<vector<char>> c {
		h+2,
		vector<char>(w+2, '.')
	};

	for (int i = 1; i <= h; ++i)
		for (int j = 1; j <= w; ++j) 
			cin >> c[i][j];

	int d1 = bfs(c, 'F'), d2 = bfs(c, 'R');

	cout << d1 + d2 << '\n';

	return 0;
}

Compilation message

tracks.cpp: In function 'int bfs(std::vector<std::vector<char> >, char)':
tracks.cpp:32:3: warning: narrowing conversion of 'n' from 'int' to 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wnarrowing]
   32 |   n,
      |   ^
tracks.cpp: In function 'int main()':
tracks.cpp:71:4: warning: narrowing conversion of '(h + 2)' from 'int' to 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wnarrowing]
   71 |   h+2,
      |   ~^~

Subtask #1
1.66666666667 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 2136 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 492 KB Output isn't correct
4 Incorrect 9 ms 1820 KB Output isn't correct
5 Incorrect 4 ms 1372 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 4 ms 1116 KB Output isn't correct
11 Incorrect 3 ms 604 KB Output isn't correct
12 Incorrect 7 ms 1112 KB Output isn't correct
13 Incorrect 4 ms 1140 KB Output isn't correct
14 Incorrect 4 ms 1372 KB Output isn't correct
15 Incorrect 17 ms 2760 KB Output isn't correct
16 Incorrect 18 ms 2324 KB Output isn't correct
17 Incorrect 13 ms 2868 KB Output isn't correct
18 Incorrect 8 ms 1628 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1368 KB Output isn't correct
2 Incorrect 87 ms 16168 KB Output isn't correct
3 Incorrect 1022 ms 164168 KB Output isn't correct
4 Incorrect 183 ms 39420 KB Output isn't correct
5 Incorrect 473 ms 99436 KB Output isn't correct
6 Incorrect 952 ms 126156 KB Output isn't correct
7 Incorrect 3 ms 1372 KB Output isn't correct
8 Incorrect 4 ms 1516 KB Output isn't correct
9 Incorrect 4 ms 1092 KB Output isn't correct
10 Incorrect 2 ms 856 KB Output isn't correct
11 Incorrect 3 ms 1372 KB Output isn't correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 86 ms 16244 KB Output isn't correct
14 Incorrect 51 ms 9564 KB Output isn't correct
15 Incorrect 61 ms 11600 KB Output isn't correct
16 Incorrect 42 ms 6756 KB Output isn't correct
17 Incorrect 272 ms 41028 KB Output isn't correct
18 Incorrect 286 ms 45520 KB Output isn't correct
19 Incorrect 240 ms 39504 KB Output isn't correct
20 Incorrect 245 ms 35380 KB Output isn't correct
21 Incorrect 581 ms 95952 KB Output isn't correct
22 Incorrect 509 ms 99436 KB Output isn't correct
23 Incorrect 551 ms 78216 KB Output isn't correct
24 Incorrect 634 ms 96160 KB Output isn't correct
25 Incorrect 1122 ms 179364 KB Output isn't correct
26 Incorrect 632 ms 135592 KB Output isn't correct
27 Incorrect 745 ms 136300 KB Output isn't correct
28 Incorrect 1028 ms 126160 KB Output isn't correct
29 Incorrect 987 ms 126876 KB Output isn't correct
30 Incorrect 852 ms 127548 KB Output isn't correct
31 Incorrect 827 ms 72272 KB Output isn't correct
32 Incorrect 857 ms 170228 KB Output isn't correct