oj.uz

답안 #767689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767689 2023-06-27T04:12:20 Z lukehsiao Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1309 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 4000;

int H, W, id[mxN][mxN];
char grid[mxN][mxN];
bool vis[mxN][mxN];

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

vector<int> dist;
queue<pair<int, int>> q;

void ff(int r, int c, int x) {
	id[r][c] = x;
	
	for (int i=0; i<4; ++i) {
		int nr = r + dx[i], nc = c + dy[i];
		if (nr >= 0 && nr < H && nc >= 0 && nc < W &&
				grid[nr][nc] == grid[r][c] && !id[nr][nc]) {
			ff(nr, nc, x);
		}
	}
}

void ff2(int r, int c) {
	vis[r][c] = true;

	for (int i=0; i<4; ++i) {
		int nr = r + dx[i], nc = c + dy[i];
		if (nr >= 0 && nr < H && nc >= 0 && nc < W &&
				!vis[nr][nc] && grid[nr][nc] != '.') {
			if (grid[nr][nc] != grid[r][c]) {
				if (dist[id[nr][nc]] == 2e9) {
					dist[id[nr][nc]] = dist[id[r][c]] + 1;
					q.push({nr, nc});
				}
			} else {
				ff2(nr, nc);
			}
		}
	}
}

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

	cin >> H >> W;
	for (int i=0; i<H; ++i)
		for (int j=0; j<W; ++j)
			cin >> grid[i][j];
	
	int cur = 0;
	for (int i=0; i<H; ++i) {
		for (int j=0; j<W; ++j) {
			if (!id[i][j] && grid[i][j] != '.')
				ff(i, j, ++cur);
		}
	}

	dist.resize(cur+1, 2e9);

	queue<pair<int, int>> q;
	q.push({0, 0});
	dist[1] = 0;

	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		ff2(r, c);
	}

	int ans = 0;
	for (int i=1; i<=cur; ++i)
		ans = max(ans, dist[i]);
	
	cout << ans + 1 << '\n';
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 7552 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Incorrect 1 ms 852 KB Output isn't correct
4 Incorrect 10 ms 8096 KB Output isn't correct
5 Incorrect 5 ms 4180 KB Output isn't correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Incorrect 1 ms 852 KB Output isn't correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Incorrect 1 ms 1560 KB Output isn't correct
10 Incorrect 3 ms 3540 KB Output isn't correct
11 Incorrect 3 ms 3284 KB Output isn't correct
12 Incorrect 6 ms 4308 KB Output isn't correct
13 Incorrect 4 ms 4180 KB Output isn't correct
14 Incorrect 4 ms 4096 KB Output isn't correct
15 Incorrect 12 ms 7480 KB Output isn't correct
16 Incorrect 14 ms 7636 KB Output isn't correct
17 Incorrect 9 ms 7296 KB Output isn't correct
18 Incorrect 9 ms 8152 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 46320 KB Output isn't correct
2 Incorrect 42 ms 21000 KB Output isn't correct
3 Incorrect 283 ms 84332 KB Output isn't correct
4 Incorrect 72 ms 41480 KB Output isn't correct
5 Incorrect 164 ms 78632 KB Output isn't correct
6 Incorrect 657 ms 140904 KB Output isn't correct
7 Incorrect 23 ms 48596 KB Output isn't correct
8 Incorrect 23 ms 46300 KB Output isn't correct
9 Incorrect 3 ms 1236 KB Output isn't correct
10 Incorrect 1 ms 848 KB Output isn't correct
11 Incorrect 22 ms 47376 KB Output isn't correct
12 Incorrect 2 ms 2260 KB Output isn't correct
13 Incorrect 42 ms 20980 KB Output isn't correct
14 Incorrect 25 ms 14588 KB Output isn't correct
15 Incorrect 25 ms 17740 KB Output isn't correct
16 Incorrect 19 ms 7872 KB Output isn't correct
17 Incorrect 96 ms 39140 KB Output isn't correct
18 Incorrect 84 ms 46224 KB Output isn't correct
19 Incorrect 73 ms 41488 KB Output isn't correct
20 Incorrect 68 ms 34168 KB Output isn't correct
21 Incorrect 163 ms 63552 KB Output isn't correct
22 Incorrect 180 ms 78356 KB Output isn't correct
23 Incorrect 187 ms 54092 KB Output isn't correct
24 Incorrect 164 ms 63172 KB Output isn't correct
25 Incorrect 307 ms 107368 KB Output isn't correct
26 Runtime error 1309 ms 1048576 KB Execution killed with signal 9
27 Incorrect 915 ms 446520 KB Output isn't correct
28 Incorrect 695 ms 137468 KB Output isn't correct
29 Incorrect 668 ms 142468 KB Output isn't correct
30 Incorrect 715 ms 186728 KB Output isn't correct
31 Incorrect 465 ms 82012 KB Output isn't correct
32 Incorrect 740 ms 368468 KB Output isn't correct