Submission #938039

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938039	2024-03-04T18:29:12 Z	TAhmed33	Tracks in the Snow (BOI13_tracks)	C++	97.8125 / 100	1534 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);
			}
		}
	}
	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	171 ms	402316 KB	Output is correct
2	Correct	139 ms	392000 KB	Output is correct
3	Correct	148 ms	392060 KB	Output is correct
4	Correct	149 ms	398816 KB	Output is correct
5	Correct	143 ms	394780 KB	Output is correct
6	Correct	136 ms	391760 KB	Output is correct
7	Correct	136 ms	392460 KB	Output is correct
8	Correct	138 ms	392272 KB	Output is correct
9	Correct	137 ms	392696 KB	Output is correct
10	Correct	139 ms	394580 KB	Output is correct
11	Correct	141 ms	394324 KB	Output is correct
12	Correct	147 ms	396472 KB	Output is correct
13	Correct	144 ms	394820 KB	Output is correct
14	Correct	141 ms	394628 KB	Output is correct
15	Correct	161 ms	400720 KB	Output is correct
16	Correct	170 ms	402268 KB	Output is correct
17	Correct	158 ms	398680 KB	Output is correct
18	Correct	149 ms	398808 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	422736 KB	Output is correct
2	Correct	244 ms	419496 KB	Output is correct
3	Correct	733 ms	529360 KB	Output is correct
4	Correct	278 ms	432976 KB	Output is correct
5	Correct	767 ms	582736 KB	Output is correct
6	Correct	1175 ms	643852 KB	Output is correct
7	Correct	147 ms	424528 KB	Output is correct
8	Correct	146 ms	422992 KB	Output is correct
9	Correct	135 ms	392792 KB	Output is correct
10	Correct	138 ms	392268 KB	Output is correct
11	Correct	154 ms	423264 KB	Output is correct
12	Correct	143 ms	393424 KB	Output is correct
13	Correct	249 ms	419568 KB	Output is correct
14	Correct	198 ms	409744 KB	Output is correct
15	Correct	186 ms	408828 KB	Output is correct
16	Correct	192 ms	404660 KB	Output is correct
17	Correct	431 ms	452180 KB	Output is correct
18	Correct	329 ms	443364 KB	Output is correct
19	Correct	274 ms	432720 KB	Output is correct
20	Correct	280 ms	433000 KB	Output is correct
21	Correct	490 ms	482996 KB	Output is correct
22	Correct	784 ms	582484 KB	Output is correct
23	Correct	669 ms	497916 KB	Output is correct
24	Correct	488 ms	484984 KB	Output is correct
25	Correct	1054 ms	550828 KB	Output is correct
26	Runtime error	574 ms	1048576 KB	Execution killed with signal 9
27	Correct	996 ms	970804 KB	Output is correct
28	Correct	1142 ms	635024 KB	Output is correct
29	Correct	1122 ms	641380 KB	Output is correct
30	Correct	1031 ms	744088 KB	Output is correct
31	Correct	1534 ms	689744 KB	Output is correct
32	Correct	990 ms	877140 KB	Output is correct