Submission #938043

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938043	2024-03-04T18:32:47 Z	TAhmed33	Tracks in the Snow (BOI13_tracks)	C++	97.8125 / 100	1518 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; 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	178 ms	406864 KB	Output is correct
2	Correct	159 ms	396908 KB	Output is correct
3	Correct	139 ms	397096 KB	Output is correct
4	Correct	159 ms	403732 KB	Output is correct
5	Correct	143 ms	399700 KB	Output is correct
6	Correct	149 ms	396908 KB	Output is correct
7	Correct	140 ms	397136 KB	Output is correct
8	Correct	138 ms	397192 KB	Output is correct
9	Correct	139 ms	397564 KB	Output is correct
10	Correct	143 ms	399384 KB	Output is correct
11	Correct	154 ms	399184 KB	Output is correct
12	Correct	149 ms	401240 KB	Output is correct
13	Correct	143 ms	399568 KB	Output is correct
14	Correct	141 ms	399700 KB	Output is correct
15	Correct	162 ms	405476 KB	Output is correct
16	Correct	170 ms	407044 KB	Output is correct
17	Correct	156 ms	403540 KB	Output is correct
18	Correct	147 ms	403548 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	427716 KB	Output is correct
2	Correct	242 ms	423344 KB	Output is correct
3	Correct	731 ms	526128 KB	Output is correct
4	Correct	279 ms	435416 KB	Output is correct
5	Correct	796 ms	582360 KB	Output is correct
6	Correct	1150 ms	640340 KB	Output is correct
7	Correct	156 ms	429280 KB	Output is correct
8	Correct	150 ms	427484 KB	Output is correct
9	Correct	139 ms	397796 KB	Output is correct
10	Correct	141 ms	397132 KB	Output is correct
11	Correct	158 ms	428432 KB	Output is correct
12	Correct	138 ms	398420 KB	Output is correct
13	Correct	243 ms	423248 KB	Output is correct
14	Correct	200 ms	413676 KB	Output is correct
15	Correct	189 ms	413140 KB	Output is correct
16	Correct	190 ms	408916 KB	Output is correct
17	Correct	411 ms	454748 KB	Output is correct
18	Correct	327 ms	445820 KB	Output is correct
19	Correct	277 ms	435540 KB	Output is correct
20	Correct	278 ms	435540 KB	Output is correct
21	Correct	494 ms	482820 KB	Output is correct
22	Correct	807 ms	582636 KB	Output is correct
23	Correct	659 ms	498260 KB	Output is correct
24	Correct	483 ms	484480 KB	Output is correct
25	Correct	1069 ms	547428 KB	Output is correct
26	Runtime error	546 ms	1048576 KB	Execution killed with signal 9
27	Correct	1004 ms	976284 KB	Output is correct
28	Correct	1161 ms	640516 KB	Output is correct
29	Correct	1081 ms	646832 KB	Output is correct
30	Correct	1061 ms	749204 KB	Output is correct
31	Correct	1518 ms	695224 KB	Output is correct
32	Correct	963 ms	882788 KB	Output is correct