oj.uz

Submission #938029

# Submission time Handle Problem Language Result Execution time Memory
938029 2024-03-04T18:10:32 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 1766 ms 1048576 KB 
            #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 () {
            	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;
            			for (auto j : adj[k]) 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 191 ms 402508 KB Output is correct
2 Correct 137 ms 391760 KB Output is correct
3 Correct 141 ms 392020 KB Output is correct
4 Correct 146 ms 398672 KB Output is correct
5 Correct 140 ms 394832 KB Output is correct
6 Correct 134 ms 391988 KB Output is correct
7 Correct 132 ms 392016 KB Output is correct
8 Correct 136 ms 392276 KB Output is correct
9 Correct 137 ms 392640 KB Output is correct
10 Correct 148 ms 394376 KB Output is correct
11 Correct 168 ms 394424 KB Output is correct
12 Correct 148 ms 396288 KB Output is correct
13 Correct 141 ms 394832 KB Output is correct
14 Correct 140 ms 394832 KB Output is correct
15 Correct 220 ms 400852 KB Output is correct
16 Correct 181 ms 402256 KB Output is correct
17 Correct 167 ms 398880 KB Output is correct
18 Correct 147 ms 399024 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 422700 KB Output is correct
2 Correct 272 ms 419408 KB Output is correct
3 Correct 1109 ms 528944 KB Output is correct
4 Correct 366 ms 432536 KB Output is correct
5 Correct 1018 ms 582120 KB Output is correct
6 Correct 1517 ms 643564 KB Output is correct
7 Correct 147 ms 424020 KB Output is correct
8 Correct 145 ms 422648 KB Output is correct
9 Correct 139 ms 393132 KB Output is correct
10 Correct 135 ms 392196 KB Output is correct
11 Correct 144 ms 423248 KB Output is correct
12 Correct 134 ms 393480 KB Output is correct
13 Correct 270 ms 419344 KB Output is correct
14 Correct 210 ms 409516 KB Output is correct
15 Correct 207 ms 409172 KB Output is correct
16 Correct 198 ms 404472 KB Output is correct
17 Correct 499 ms 451892 KB Output is correct
18 Correct 429 ms 443144 KB Output is correct
19 Correct 356 ms 432720 KB Output is correct
20 Correct 361 ms 432668 KB Output is correct
21 Correct 714 ms 482952 KB Output is correct
22 Correct 1040 ms 581904 KB Output is correct
23 Correct 854 ms 497744 KB Output is correct
24 Correct 706 ms 484376 KB Output is correct
25 Correct 1471 ms 542440 KB Output is correct
26 Runtime error 847 ms 1048576 KB Execution killed with signal 9
27 Correct 1740 ms 979340 KB Output is correct
28 Correct 1531 ms 643156 KB Output is correct
29 Correct 1455 ms 649748 KB Output is correct
30 Correct 1439 ms 751808 KB Output is correct
31 Correct 1766 ms 695456 KB Output is correct
32 Correct 1350 ms 885240 KB Output is correct