oj.uz

답안 #1095584

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095584 2024-10-02T15:15:19 Z mat_jur Tracks in the Snow (BOI13_tracks) C++17
4.375 / 100
 569 ms 210576 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) {
	int n = ssize(c), m = ssize(c[0]);

	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;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (c[i][j] == '.') {
				q.push_back({i, j});
				dist[i][j] = 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) 
			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];

	cout << bfs(c) << '\n';

	return 0;
}

Compilation message

tracks.cpp: In function 'int bfs(std::vector<std::vector<char> >)':
tracks.cpp:27:3: warning: narrowing conversion of 'n' from 'int' to 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wnarrowing]
   27 |   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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 2140 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 5 ms 1628 KB Output isn't correct
5 Incorrect 3 ms 1372 KB Output isn't correct
6 Incorrect 1 ms 344 KB Output isn't correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 1 ms 604 KB Output isn't correct
10 Incorrect 2 ms 1116 KB Output isn't correct
11 Incorrect 2 ms 604 KB Output isn't correct
12 Incorrect 4 ms 1116 KB Output isn't correct
13 Incorrect 3 ms 1400 KB Output isn't correct
14 Incorrect 3 ms 1368 KB Output isn't correct
15 Incorrect 14 ms 2772 KB Output isn't correct
16 Incorrect 9 ms 2332 KB Output isn't correct
17 Incorrect 8 ms 3164 KB Output isn't correct
18 Incorrect 5 ms 1628 KB Output isn't correct

Subtask #2
4.375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1628 KB Output isn't correct
2 Incorrect 46 ms 18796 KB Output isn't correct
3 Incorrect 452 ms 210576 KB Output isn't correct
4 Incorrect 167 ms 52488 KB Output isn't correct
5 Incorrect 236 ms 99800 KB Output isn't correct
6 Incorrect 547 ms 126136 KB Output isn't correct
7 Incorrect 3 ms 1372 KB Output isn't correct
8 Incorrect 2 ms 1676 KB Output isn't correct
9 Incorrect 2 ms 976 KB Output isn't correct
10 Incorrect 1 ms 788 KB Output isn't correct
11 Incorrect 2 ms 1628 KB Output isn't correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 42 ms 18656 KB Output isn't correct
14 Incorrect 24 ms 11100 KB Output isn't correct
15 Incorrect 29 ms 13208 KB Output isn't correct
16 Incorrect 18 ms 7104 KB Output isn't correct
17 Incorrect 110 ms 48172 KB Output isn't correct
18 Incorrect 120 ms 51832 KB Output isn't correct
19 Incorrect 109 ms 52248 KB Output isn't correct
20 Incorrect 99 ms 45064 KB Output isn't correct
21 Incorrect 247 ms 122712 KB Output isn't correct
22 Incorrect 221 ms 99668 KB Output isn't correct
23 Incorrect 218 ms 90900 KB Output isn't correct
24 Incorrect 230 ms 113236 KB Output isn't correct
25 Incorrect 515 ms 204536 KB Output isn't correct
26 Correct 397 ms 134968 KB Output is correct
27 Correct 469 ms 136196 KB Output is correct
28 Incorrect 569 ms 126064 KB Output isn't correct
29 Incorrect 555 ms 126680 KB Output isn't correct
30 Incorrect 516 ms 130196 KB Output isn't correct
31 Incorrect 403 ms 72272 KB Output isn't correct
32 Incorrect 470 ms 133888 KB Output isn't correct