#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
int n, m, component[4000][4000], ans = 1;
char snow[4000][4000];
int num = 1;
vector<int> graph[16000050];
int visited[16000050];
void floodfill(int c, int x, int y) {
component[x][y] = c;
if (x > 0 && snow[x - 1][y] != '.') {
if (snow[x - 1][y] == snow[x][y] && !component[x - 1][y]) floodfill(c, x - 1, y);
else if (component[x - 1][y]) {
graph[c].push_back(component[x - 1][y]);
graph[component[x - 1][y]].push_back(c);
}
}
if (x < n - 1 && snow[x + 1][y] != '.') {
if (snow[x + 1][y] == snow[x][y] && !component[x + 1][y]) floodfill(c, x + 1, y);
else if (component[x + 1][y]) {
graph[c].push_back(component[x + 1][y]);
graph[component[x + 1][y]].push_back(c);
}
}
if (y > 0 && snow[x][y - 1] != '.') {
if (snow[x][y - 1] == snow[x][y] && !component[x][y - 1]) floodfill(c, x, y - 1);
else if (component[x][y - 1]) {
graph[c].push_back(component[x][y - 1]);
graph[component[x][y - 1]].push_back(c);
}
}
if (y < m - 1 && snow[x][y + 1] != '.') {
if (snow[x][y + 1] == snow[x][y] && !component[x][y + 1]) floodfill(c, x, y + 1);
else if (component[x][y + 1]) {
graph[c].push_back(component[x][y+ 1]);
graph[component[x][y + 1]].push_back(c);
}
}
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
FOR(i, 0, n) FOR(j, 0, m) cin >> snow[i][j];
FOR(i, 0, n) FOR(j, 0, m) {
if (!component[i][j] && snow[i][j] != '.') {
floodfill(num++, i, j);
}
}
queue<int> q;
q.push(1);
visited[1] = 1;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int i : graph[curr]) {
if (!visited[i]) {
visited[i] = visited[curr] + 1;
ans = max(ans, visited[i]);
q.push(i);
}
}
}
cout << ans;
return 0;
}
Compilation message
tracks.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
#pragma GCC Optimize("unroll-loops")
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
395 ms |
387144 KB |
Output is correct |
2 |
Correct |
343 ms |
376304 KB |
Output is correct |
3 |
Correct |
344 ms |
376492 KB |
Output is correct |
4 |
Correct |
376 ms |
385464 KB |
Output is correct |
5 |
Correct |
348 ms |
379260 KB |
Output is correct |
6 |
Correct |
340 ms |
376204 KB |
Output is correct |
7 |
Correct |
339 ms |
376524 KB |
Output is correct |
8 |
Correct |
352 ms |
376764 KB |
Output is correct |
9 |
Correct |
352 ms |
376916 KB |
Output is correct |
10 |
Correct |
357 ms |
378808 KB |
Output is correct |
11 |
Correct |
357 ms |
379332 KB |
Output is correct |
12 |
Correct |
371 ms |
380956 KB |
Output is correct |
13 |
Correct |
360 ms |
379256 KB |
Output is correct |
14 |
Correct |
350 ms |
379256 KB |
Output is correct |
15 |
Correct |
394 ms |
385584 KB |
Output is correct |
16 |
Correct |
398 ms |
387228 KB |
Output is correct |
17 |
Correct |
379 ms |
383432 KB |
Output is correct |
18 |
Correct |
367 ms |
385444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
373 ms |
407256 KB |
Output is correct |
2 |
Correct |
504 ms |
406280 KB |
Output is correct |
3 |
Correct |
1275 ms |
535588 KB |
Output is correct |
4 |
Correct |
563 ms |
421032 KB |
Output is correct |
5 |
Correct |
1253 ms |
587604 KB |
Output is correct |
6 |
Execution timed out |
2135 ms |
845188 KB |
Time limit exceeded |
7 |
Correct |
379 ms |
408780 KB |
Output is correct |
8 |
Correct |
380 ms |
407216 KB |
Output is correct |
9 |
Correct |
351 ms |
377352 KB |
Output is correct |
10 |
Correct |
347 ms |
376520 KB |
Output is correct |
11 |
Correct |
379 ms |
407780 KB |
Output is correct |
12 |
Correct |
346 ms |
377756 KB |
Output is correct |
13 |
Correct |
500 ms |
406368 KB |
Output is correct |
14 |
Correct |
435 ms |
395304 KB |
Output is correct |
15 |
Correct |
428 ms |
394940 KB |
Output is correct |
16 |
Correct |
419 ms |
390140 KB |
Output is correct |
17 |
Correct |
748 ms |
443484 KB |
Output is correct |
18 |
Correct |
671 ms |
434728 KB |
Output is correct |
19 |
Correct |
558 ms |
421100 KB |
Output is correct |
20 |
Correct |
568 ms |
421548 KB |
Output is correct |
21 |
Correct |
911 ms |
480024 KB |
Output is correct |
22 |
Correct |
1256 ms |
587596 KB |
Output is correct |
23 |
Correct |
1099 ms |
496036 KB |
Output is correct |
24 |
Correct |
940 ms |
487740 KB |
Output is correct |
25 |
Correct |
1831 ms |
561840 KB |
Output is correct |
26 |
Runtime error |
1361 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
27 |
Execution timed out |
2133 ms |
1028708 KB |
Time limit exceeded |
28 |
Execution timed out |
2075 ms |
825712 KB |
Time limit exceeded |
29 |
Execution timed out |
2103 ms |
814436 KB |
Time limit exceeded |
30 |
Execution timed out |
2079 ms |
884812 KB |
Time limit exceeded |
31 |
Execution timed out |
2069 ms |
710200 KB |
Time limit exceeded |
32 |
Execution timed out |
2151 ms |
968840 KB |
Time limit exceeded |