Submission #938031

# Submission time Handle Problem Language Result Execution time Memory
938031 2024-03-04T18:13:19 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
0 / 100
507 ms 1048576 KB
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int comp[4001][4001];
char arr[4001][4001]; 
int n, m;
bool check (int i, int j) {
	return (i >= 1 && i <= n && j >= 1 && 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]);
		}
	}
}
queue <int> adj[16000001];
bool vis[16000001];
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	memset(vis, false, sizeof(vis));
	cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> arr[i][j];
	int c = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (comp[i][j] == 0 && arr[i][j] != '.') {
				c++;
				comp[i][j] = c;
				dfs(i, j);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; 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(comp[i + dx[l]][j + dy[l]]);
						adj[comp[i + dx[l]][j + dy[l]]].push(comp[i][j]);
					}
				}
			}
		}
	}
 
	queue <int> cur;
	cur.push(comp[1][1]); vis[comp[1][1]] = 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].front();
				adj[k].pop();
				if (!vis[j]) {
					vis[j] = 1; cur.push(j);
				}
			}
		}
		cnt++;
	}
	cout << ans << '\n';
}
# Verdict Execution time Memory Grader output
1 Runtime error 396 ms 1048576 KB Execution killed with signal 9
2 Runtime error 373 ms 1048576 KB Execution killed with signal 9
3 Runtime error 382 ms 1048576 KB Execution killed with signal 9
4 Runtime error 385 ms 1048576 KB Execution killed with signal 9
5 Runtime error 375 ms 1048576 KB Execution killed with signal 9
6 Runtime error 449 ms 1048576 KB Execution killed with signal 9
7 Runtime error 369 ms 1048576 KB Execution killed with signal 9
8 Runtime error 399 ms 1048576 KB Execution killed with signal 9
9 Runtime error 381 ms 1048576 KB Execution killed with signal 9
10 Runtime error 358 ms 1048576 KB Execution killed with signal 9
11 Runtime error 374 ms 1048576 KB Execution killed with signal 9
12 Runtime error 370 ms 1048576 KB Execution killed with signal 9
13 Runtime error 380 ms 1048576 KB Execution killed with signal 9
14 Runtime error 410 ms 1048576 KB Execution killed with signal 9
15 Runtime error 411 ms 1048576 KB Execution killed with signal 9
16 Runtime error 362 ms 1048576 KB Execution killed with signal 9
17 Runtime error 372 ms 1048576 KB Execution killed with signal 9
18 Runtime error 360 ms 1048576 KB Execution killed with signal 9
# Verdict Execution time Memory Grader output
1 Runtime error 374 ms 1048576 KB Execution killed with signal 9
2 Runtime error 384 ms 1048576 KB Execution killed with signal 9
3 Runtime error 390 ms 1048576 KB Execution killed with signal 9
4 Runtime error 376 ms 1048576 KB Execution killed with signal 9
5 Runtime error 399 ms 1048576 KB Execution killed with signal 9
6 Runtime error 405 ms 1048576 KB Execution killed with signal 9
7 Runtime error 359 ms 1048576 KB Execution killed with signal 9
8 Runtime error 374 ms 1048576 KB Execution killed with signal 9
9 Runtime error 358 ms 1048576 KB Execution killed with signal 9
10 Runtime error 363 ms 1048576 KB Execution killed with signal 9
11 Runtime error 372 ms 1048576 KB Execution killed with signal 9
12 Runtime error 372 ms 1048576 KB Execution killed with signal 9
13 Runtime error 361 ms 1048576 KB Execution killed with signal 9
14 Runtime error 507 ms 1048576 KB Execution killed with signal 9
15 Runtime error 399 ms 1048576 KB Execution killed with signal 9
16 Runtime error 357 ms 1048576 KB Execution killed with signal 9
17 Runtime error 369 ms 1048576 KB Execution killed with signal 9
18 Runtime error 383 ms 1048576 KB Execution killed with signal 9
19 Runtime error 382 ms 1048576 KB Execution killed with signal 9
20 Runtime error 380 ms 1048576 KB Execution killed with signal 9
21 Runtime error 380 ms 1048576 KB Execution killed with signal 9
22 Runtime error 386 ms 1048576 KB Execution killed with signal 9
23 Runtime error 367 ms 1048576 KB Execution killed with signal 9
24 Runtime error 368 ms 1048576 KB Execution killed with signal 9
25 Runtime error 386 ms 1048576 KB Execution killed with signal 9
26 Runtime error 363 ms 1048576 KB Execution killed with signal 9
27 Runtime error 372 ms 1048576 KB Execution killed with signal 9
28 Runtime error 371 ms 1048576 KB Execution killed with signal 9
29 Runtime error 390 ms 1048576 KB Execution killed with signal 9
30 Runtime error 378 ms 1048576 KB Execution killed with signal 9
31 Runtime error 376 ms 1048576 KB Execution killed with signal 9
32 Runtime error 363 ms 1048576 KB Execution killed with signal 9