Submission #938036

# Submission time Handle Problem Language Result Execution time Memory
938036 2024-03-04T18:27:30 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
1601 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]);
		}
	}
}
vector <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_back(comp[i + dx[l]][j + dy[l]]);
						adj[comp[i + dx[l]][j + dy[l]]].push_back(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].back();
				adj[k].pop_back();
				if (!vis[j]) {
					vis[j] = 1; cur.push(j);
				}
			}
		}
		cnt++;
	}
	cout << ans << '\n';
}
# Verdict Execution time Memory Grader output
1 Correct 178 ms 402260 KB Output is correct
2 Correct 130 ms 391960 KB Output is correct
3 Correct 127 ms 392272 KB Output is correct
4 Correct 138 ms 398796 KB Output is correct
5 Correct 133 ms 394836 KB Output is correct
6 Correct 128 ms 391760 KB Output is correct
7 Correct 130 ms 392136 KB Output is correct
8 Correct 127 ms 392272 KB Output is correct
9 Correct 136 ms 392924 KB Output is correct
10 Correct 134 ms 394400 KB Output is correct
11 Correct 133 ms 394328 KB Output is correct
12 Correct 139 ms 396424 KB Output is correct
13 Correct 137 ms 394832 KB Output is correct
14 Correct 131 ms 394832 KB Output is correct
15 Correct 156 ms 400724 KB Output is correct
16 Correct 166 ms 402608 KB Output is correct
17 Correct 147 ms 398676 KB Output is correct
18 Correct 140 ms 398828 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 163 ms 422600 KB Output is correct
2 Correct 235 ms 419664 KB Output is correct
3 Correct 813 ms 529492 KB Output is correct
4 Correct 271 ms 432724 KB Output is correct
5 Correct 905 ms 582260 KB Output is correct
6 Correct 1225 ms 643640 KB Output is correct
7 Correct 143 ms 424276 KB Output is correct
8 Correct 140 ms 422660 KB Output is correct
9 Correct 136 ms 392996 KB Output is correct
10 Correct 129 ms 392324 KB Output is correct
11 Correct 144 ms 423392 KB Output is correct
12 Correct 133 ms 393372 KB Output is correct
13 Correct 250 ms 419668 KB Output is correct
14 Correct 194 ms 409536 KB Output is correct
15 Correct 189 ms 408920 KB Output is correct
16 Correct 185 ms 404572 KB Output is correct
17 Correct 407 ms 451924 KB Output is correct
18 Correct 330 ms 443132 KB Output is correct
19 Correct 267 ms 432968 KB Output is correct
20 Correct 281 ms 433232 KB Output is correct
21 Correct 507 ms 482716 KB Output is correct
22 Correct 880 ms 582044 KB Output is correct
23 Correct 681 ms 498064 KB Output is correct
24 Correct 546 ms 484840 KB Output is correct
25 Correct 1069 ms 550428 KB Output is correct
26 Runtime error 611 ms 1048576 KB Execution killed with signal 9
27 Correct 1059 ms 979416 KB Output is correct
28 Correct 1192 ms 643396 KB Output is correct
29 Correct 1167 ms 650156 KB Output is correct
30 Correct 1105 ms 751748 KB Output is correct
31 Correct 1601 ms 695464 KB Output is correct
32 Correct 1058 ms 885604 KB Output is correct