///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 4010;
vector<int> adj[N * N], cost[N * N];
char g[N][N];
int d[N * N], n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int id(int x, int y) { return x * m + y; }
void addEdge(int u, int v, int c) {
adj[u].push_back(v);
cost[u].push_back(c);
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf(" %s", g[i]);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) if(g[i][j] != '.') {
for(int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if(x >= 0 && x < n && y > 0 && y < m && g[x][y] != '.') {
int c = g[i][j] != g[x][y];
addEdge(id(i, j), id(x, y), c);
}
}
}
}
deque<int> q;
memset(d, 63, sizeof d);
d[0] = 0;
q.push_back(0);
while(!q.empty()) {
int u = q.front(); q.pop_front();
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(d[v] > d[u] + c) {
d[v] = d[u] + c;
if(c) q.push_back(v);
else q.push_front(v);
}
}
}
int mx = 0;
for(int i = 0; i < n * m; i++) {
if(d[i] <= n * m) mx = max(mx, d[i]);
}
printf("%d\n", 1 + mx);
}
Compilation message
tracks.cpp: In function 'int main()':
tracks.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
tracks.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", g[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1321 ms |
835432 KB |
Output isn't correct |
| 2 |
Incorrect |
779 ms |
835432 KB |
Output isn't correct |
| 3 |
Correct |
810 ms |
835432 KB |
Output is correct |
| 4 |
Correct |
917 ms |
835432 KB |
Output is correct |
| 5 |
Correct |
801 ms |
835432 KB |
Output is correct |
| 6 |
Incorrect |
750 ms |
835432 KB |
Output isn't correct |
| 7 |
Correct |
711 ms |
835432 KB |
Output is correct |
| 8 |
Incorrect |
744 ms |
835432 KB |
Output isn't correct |
| 9 |
Correct |
724 ms |
835432 KB |
Output is correct |
| 10 |
Correct |
731 ms |
835432 KB |
Output is correct |
| 11 |
Incorrect |
756 ms |
835432 KB |
Output isn't correct |
| 12 |
Incorrect |
834 ms |
835432 KB |
Output isn't correct |
| 13 |
Correct |
796 ms |
835432 KB |
Output is correct |
| 14 |
Correct |
737 ms |
835432 KB |
Output is correct |
| 15 |
Correct |
890 ms |
835432 KB |
Output is correct |
| 16 |
Incorrect |
905 ms |
837108 KB |
Output isn't correct |
| 17 |
Incorrect |
857 ms |
837108 KB |
Output isn't correct |
| 18 |
Correct |
825 ms |
837108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
773 ms |
837108 KB |
Output isn't correct |
| 2 |
Incorrect |
1175 ms |
868124 KB |
Output isn't correct |
| 3 |
Execution timed out |
2124 ms |
1008988 KB |
Time limit exceeded |
| 4 |
Correct |
1074 ms |
1008988 KB |
Output is correct |
| 5 |
Execution timed out |
2143 ms |
1049600 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2089 ms |
1049600 KB |
Time limit exceeded |
| 7 |
Runtime error |
761 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 8 |
Runtime error |
718 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 9 |
Runtime error |
853 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 10 |
Runtime error |
795 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 11 |
Runtime error |
720 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 12 |
Runtime error |
777 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 13 |
Runtime error |
1131 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 14 |
Runtime error |
991 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 15 |
Runtime error |
851 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 16 |
Runtime error |
950 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 17 |
Runtime error |
1500 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 18 |
Runtime error |
1154 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 19 |
Runtime error |
1188 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 20 |
Runtime error |
1191 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 21 |
Runtime error |
1851 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 22 |
Execution timed out |
2128 ms |
1049600 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2163 ms |
1049600 KB |
Time limit exceeded |
| 24 |
Runtime error |
1785 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 25 |
Execution timed out |
2080 ms |
1049600 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2191 ms |
1049600 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2138 ms |
1049600 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2155 ms |
1049600 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2125 ms |
1049600 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2134 ms |
1049600 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2124 ms |
1049600 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2150 ms |
1049600 KB |
Time limit exceeded |
