Submission #938042

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938042	2024-03-04T18:30:32 Z	TAhmed33	Tracks in the Snow (BOI13_tracks)	C++	97.8125 / 100	1527 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 = 4000;
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	187 ms	402004 KB	Output is correct
2	Correct	138 ms	391996 KB	Output is correct
3	Correct	139 ms	392272 KB	Output is correct
4	Correct	149 ms	398540 KB	Output is correct
5	Correct	143 ms	394580 KB	Output is correct
6	Correct	149 ms	391764 KB	Output is correct
7	Correct	141 ms	392440 KB	Output is correct
8	Correct	143 ms	392440 KB	Output is correct
9	Correct	140 ms	392688 KB	Output is correct
10	Correct	146 ms	394328 KB	Output is correct
11	Correct	141 ms	394324 KB	Output is correct
12	Correct	151 ms	396188 KB	Output is correct
13	Correct	143 ms	394632 KB	Output is correct
14	Correct	142 ms	394756 KB	Output is correct
15	Correct	164 ms	400404 KB	Output is correct
16	Correct	188 ms	402008 KB	Output is correct
17	Correct	160 ms	398512 KB	Output is correct
18	Correct	153 ms	399056 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	422780 KB	Output is correct
2	Correct	245 ms	418384 KB	Output is correct
3	Correct	723 ms	520736 KB	Output is correct
4	Correct	279 ms	430660 KB	Output is correct
5	Correct	786 ms	577360 KB	Output is correct
6	Correct	1156 ms	635128 KB	Output is correct
7	Correct	153 ms	424272 KB	Output is correct
8	Correct	157 ms	422924 KB	Output is correct
9	Correct	143 ms	392788 KB	Output is correct
10	Correct	143 ms	392276 KB	Output is correct
11	Correct	152 ms	423252 KB	Output is correct
12	Correct	144 ms	393392 KB	Output is correct
13	Correct	244 ms	418388 KB	Output is correct
14	Correct	197 ms	408660 KB	Output is correct
15	Correct	189 ms	408400 KB	Output is correct
16	Correct	188 ms	404056 KB	Output is correct
17	Correct	407 ms	449828 KB	Output is correct
18	Correct	332 ms	441140 KB	Output is correct
19	Correct	272 ms	430448 KB	Output is correct
20	Correct	281 ms	430780 KB	Output is correct
21	Correct	487 ms	477884 KB	Output is correct
22	Correct	792 ms	577236 KB	Output is correct
23	Correct	666 ms	493352 KB	Output is correct
24	Correct	488 ms	479828 KB	Output is correct
25	Correct	1048 ms	542028 KB	Output is correct
26	Runtime error	585 ms	1048576 KB	Execution killed with signal 9
27	Correct	1014 ms	971164 KB	Output is correct
28	Correct	1149 ms	635020 KB	Output is correct
29	Correct	1078 ms	641532 KB	Output is correct
30	Correct	1048 ms	743832 KB	Output is correct
31	Correct	1527 ms	690088 KB	Output is correct
32	Correct	960 ms	877064 KB	Output is correct