oj.uz

답안 #938039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938039 2024-03-04T18:29:12 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 1534 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
const int MAXN = 4000;
int comp[MAXN][MAXN];
char arr[MAXN][MAXN]; 
int n, m;
bool check (int i, int j) {
	return (i >= 0 && i < n && j >= 0 && j < m && arr[i][j] != '.');
}
void dfs (int i, int j) {
	for (int l = 0; l < 4; l++) {
		if (check(i + dx[l], j + dy[l]) && comp[i + dx[l]][j + dy[l]] == 0 && arr[i + dx[l]][j + dy[l]] == arr[i][j]) {
			comp[i + dx[l]][j + dy[l]] = comp[i][j];
			dfs(i + dx[l], j + dy[l]);
		}
	}
}
vector <int> adj[MAXN * MAXN];
bool vis[MAXN * MAXN];
queue <int> cur;
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	memset(vis, false, sizeof(vis));
	cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> arr[i][j];
	int c = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (comp[i][j] == 0 && arr[i][j] != '.') {
				c++;
				comp[i][j] = c;
				dfs(i, j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == '.') continue;
			for (int l = 0; l < 4; l++) {
				if (check(i + dx[l], j + dy[l])) {
					if (comp[i + dx[l]][j + dy[l]] != comp[i][j]) {
						adj[comp[i][j]].push_back(comp[i + dx[l]][j + dy[l]]);
						adj[comp[i + dx[l]][j + dy[l]]].push_back(comp[i][j]);
					}
				}
			}
		}
	}
 	cur.push(comp[0][0]); vis[comp[0][0]] = 1;
	int cnt = 1;
	int ans = 0;
	while (!cur.empty()) {
		auto u = cur.size(); while (u--) {
			int k = cur.front(); cur.pop(); 
			ans = cnt;
			while (!adj[k].empty()) {
				int j = adj[k].back();
				adj[k].pop_back();
				if (!vis[j]) {
					vis[j] = 1; cur.push(j);
				}
			}
		}
		cnt++;
	}
	cout << ans << '\n';
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 402316 KB Output is correct
2 Correct 139 ms 392000 KB Output is correct
3 Correct 148 ms 392060 KB Output is correct
4 Correct 149 ms 398816 KB Output is correct
5 Correct 143 ms 394780 KB Output is correct
6 Correct 136 ms 391760 KB Output is correct
7 Correct 136 ms 392460 KB Output is correct
8 Correct 138 ms 392272 KB Output is correct
9 Correct 137 ms 392696 KB Output is correct
10 Correct 139 ms 394580 KB Output is correct
11 Correct 141 ms 394324 KB Output is correct
12 Correct 147 ms 396472 KB Output is correct
13 Correct 144 ms 394820 KB Output is correct
14 Correct 141 ms 394628 KB Output is correct
15 Correct 161 ms 400720 KB Output is correct
16 Correct 170 ms 402268 KB Output is correct
17 Correct 158 ms 398680 KB Output is correct
18 Correct 149 ms 398808 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 422736 KB Output is correct
2 Correct 244 ms 419496 KB Output is correct
3 Correct 733 ms 529360 KB Output is correct
4 Correct 278 ms 432976 KB Output is correct
5 Correct 767 ms 582736 KB Output is correct
6 Correct 1175 ms 643852 KB Output is correct
7 Correct 147 ms 424528 KB Output is correct
8 Correct 146 ms 422992 KB Output is correct
9 Correct 135 ms 392792 KB Output is correct
10 Correct 138 ms 392268 KB Output is correct
11 Correct 154 ms 423264 KB Output is correct
12 Correct 143 ms 393424 KB Output is correct
13 Correct 249 ms 419568 KB Output is correct
14 Correct 198 ms 409744 KB Output is correct
15 Correct 186 ms 408828 KB Output is correct
16 Correct 192 ms 404660 KB Output is correct
17 Correct 431 ms 452180 KB Output is correct
18 Correct 329 ms 443364 KB Output is correct
19 Correct 274 ms 432720 KB Output is correct
20 Correct 280 ms 433000 KB Output is correct
21 Correct 490 ms 482996 KB Output is correct
22 Correct 784 ms 582484 KB Output is correct
23 Correct 669 ms 497916 KB Output is correct
24 Correct 488 ms 484984 KB Output is correct
25 Correct 1054 ms 550828 KB Output is correct
26 Runtime error 574 ms 1048576 KB Execution killed with signal 9
27 Correct 996 ms 970804 KB Output is correct
28 Correct 1142 ms 635024 KB Output is correct
29 Correct 1122 ms 641380 KB Output is correct
30 Correct 1031 ms 744088 KB Output is correct
31 Correct 1534 ms 689744 KB Output is correct
32 Correct 990 ms 877140 KB Output is correct