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

tracks

#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';
}

Subtask #1

30.0 / 30.0

#	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

Subtask #2

67.8125 / 70.0

#	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