Submission #938044

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938044	2024-03-04T18:33:42 Z	TAhmed33	Tracks in the Snow (BOI13_tracks)	C++	97.8125 / 100	1553 ms	1048576 KB

tracks

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
const int MAXN = 4025;
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; assert(n < MAXN); assert(m < MAXN); 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);
			}
		}
	}
	assert(c < MAXN * MAXN);
	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

#	Verdict	Execution time	Memory	Grader output
1	Correct	200 ms	406864 KB	Output is correct
2	Correct	140 ms	397140 KB	Output is correct
3	Correct	133 ms	397136 KB	Output is correct
4	Correct	143 ms	403640 KB	Output is correct
5	Correct	140 ms	399696 KB	Output is correct
6	Correct	138 ms	397116 KB	Output is correct
7	Correct	137 ms	397136 KB	Output is correct
8	Correct	134 ms	397140 KB	Output is correct
9	Correct	139 ms	397532 KB	Output is correct
10	Correct	139 ms	399240 KB	Output is correct
11	Correct	137 ms	399184 KB	Output is correct
12	Correct	145 ms	401236 KB	Output is correct
13	Correct	144 ms	400040 KB	Output is correct
14	Correct	139 ms	399696 KB	Output is correct
15	Correct	163 ms	405460 KB	Output is correct
16	Correct	168 ms	406868 KB	Output is correct
17	Correct	158 ms	403536 KB	Output is correct
18	Correct	149 ms	403664 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	427668 KB	Output is correct
2	Correct	236 ms	423304 KB	Output is correct
3	Correct	731 ms	526396 KB	Output is correct
4	Correct	268 ms	435540 KB	Output is correct
5	Correct	761 ms	582276 KB	Output is correct
6	Correct	1176 ms	640612 KB	Output is correct
7	Correct	150 ms	429308 KB	Output is correct
8	Correct	146 ms	427616 KB	Output is correct
9	Correct	136 ms	397656 KB	Output is correct
10	Correct	135 ms	397140 KB	Output is correct
11	Correct	144 ms	428284 KB	Output is correct
12	Correct	135 ms	398332 KB	Output is correct
13	Correct	235 ms	423076 KB	Output is correct
14	Correct	195 ms	413700 KB	Output is correct
15	Correct	181 ms	412968 KB	Output is correct
16	Correct	188 ms	409040 KB	Output is correct
17	Correct	412 ms	454728 KB	Output is correct
18	Correct	326 ms	445776 KB	Output is correct
19	Correct	269 ms	435436 KB	Output is correct
20	Correct	277 ms	435532 KB	Output is correct
21	Correct	489 ms	482896 KB	Output is correct
22	Correct	755 ms	582404 KB	Output is correct
23	Correct	683 ms	498616 KB	Output is correct
24	Correct	496 ms	484692 KB	Output is correct
25	Correct	1012 ms	547188 KB	Output is correct
26	Runtime error	588 ms	1048576 KB	Execution killed with signal 9
27	Correct	991 ms	976312 KB	Output is correct
28	Correct	1169 ms	640560 KB	Output is correct
29	Correct	1128 ms	646948 KB	Output is correct
30	Correct	1063 ms	749592 KB	Output is correct
31	Correct	1553 ms	695180 KB	Output is correct
32	Correct	965 ms	882520 KB	Output is correct