#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5 +5, inf = INT_MAX, LL = 30;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int comp[4005][4005];
unordered_map<int,int> edg[4005];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
void rush(){
int n,m;
cin>>n>>m;
vector<vector<char>> arr(n,vector<char>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
comp[i][j]=-1;
cin>>arr[i][j];
}
}
int ct = 0;
int u,v,a,b;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]!='.' && comp[i][j]==-1){
queue<pair<int,int>> q;
q.push({i,j});
comp[i][j]=ct;
while(!q.empty()){
pair<int,int> node = q.front();q.pop();
for(int x=0;x<4;x++){
a = node.first + dx[x];
b = node.second + dy[x];
if(a>=0 && a<n && b>=0 && b<m && comp[a][b]==-1 && arr[a][b]==arr[i][j]){
comp[a][b]=ct;
q.push({a,b});
}
}
}
ct++;
}
}
}
vector<int> graph[ct];
for(int i =0;i<n;i++){
for(int j=0;j<m;j++){
if(comp[i][j]!=-1){
for(int x= 0; x<4;x++){
a = i + dx[x];
b = j + dy[x];
if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){
u = min(comp[i][j],comp[a][b]);
v =max(comp[i][j],comp[a][b]);
if(edg[u][v]==0 ){
edg[u][v]=1;
graph[u].pb(v);
graph[v].pb(u);
}
}
}
}
}
}
int ans=0;
queue<pair<int,int>> q;
vector<int> used(ct,0);
q.push({0,1});
used[0]=1;
while(!q.empty()){
auto node = q.front();
ans=max(ans,node.second);
q.pop();
for(auto v:graph[node.first]){
if(!used[v]){
used[v]=1;
q.push({v,node.second+1});
}
}
}
putr(ans);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
rush();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
37448 KB |
Execution killed with signal 8 |
| 2 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 4 |
Correct |
10 ms |
17656 KB |
Output is correct |
| 5 |
Runtime error |
26 ms |
23632 KB |
Execution killed with signal 8 |
| 6 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4832 KB |
Output is correct |
| 10 |
Runtime error |
21 ms |
19180 KB |
Execution killed with signal 8 |
| 11 |
Correct |
4 ms |
9040 KB |
Output is correct |
| 12 |
Runtime error |
34 ms |
23716 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
25 ms |
23632 KB |
Execution killed with signal 8 |
| 14 |
Runtime error |
27 ms |
23632 KB |
Execution killed with signal 8 |
| 15 |
Runtime error |
41 ms |
37572 KB |
Execution killed with signal 8 |
| 16 |
Runtime error |
46 ms |
37464 KB |
Execution killed with signal 8 |
| 17 |
Runtime error |
42 ms |
37448 KB |
Execution killed with signal 11 |
| 18 |
Correct |
11 ms |
17744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
180 ms |
248676 KB |
Execution killed with signal 8 |
| 2 |
Runtime error |
114 ms |
97864 KB |
Execution killed with signal 8 |
| 3 |
Runtime error |
560 ms |
357192 KB |
Execution killed with signal 8 |
| 4 |
Runtime error |
168 ms |
142716 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
603 ms |
430060 KB |
Execution killed with signal 8 |
| 6 |
Runtime error |
809 ms |
313672 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
163 ms |
256840 KB |
Execution killed with signal 8 |
| 8 |
Runtime error |
155 ms |
248440 KB |
Execution killed with signal 8 |
| 9 |
Runtime error |
13 ms |
6748 KB |
Execution killed with signal 8 |
| 10 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 11 |
Correct |
13 ms |
124360 KB |
Output is correct |
| 12 |
Runtime error |
17 ms |
15196 KB |
Execution killed with signal 8 |
| 13 |
Runtime error |
106 ms |
98300 KB |
Execution killed with signal 8 |
| 14 |
Runtime error |
71 ms |
67652 KB |
Execution killed with signal 8 |
| 15 |
Runtime error |
91 ms |
77640 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
55 ms |
37192 KB |
Execution killed with signal 8 |
| 17 |
Runtime error |
227 ms |
163680 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
247 ms |
165700 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
194 ms |
143948 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
169 ms |
137800 KB |
Execution killed with signal 8 |
| 21 |
Runtime error |
397 ms |
264992 KB |
Execution killed with signal 8 |
| 22 |
Runtime error |
653 ms |
430152 KB |
Execution killed with signal 8 |
| 23 |
Runtime error |
365 ms |
230728 KB |
Execution killed with signal 8 |
| 24 |
Runtime error |
451 ms |
296168 KB |
Execution killed with signal 8 |
| 25 |
Runtime error |
745 ms |
405252 KB |
Execution killed with signal 8 |
| 26 |
Correct |
423 ms |
130120 KB |
Output is correct |
| 27 |
Runtime error |
672 ms |
288848 KB |
Execution killed with signal 8 |
| 28 |
Runtime error |
875 ms |
319980 KB |
Execution killed with signal 11 |
| 29 |
Runtime error |
835 ms |
303440 KB |
Execution killed with signal 8 |
| 30 |
Runtime error |
747 ms |
293716 KB |
Execution killed with signal 11 |
| 31 |
Runtime error |
757 ms |
291412 KB |
Execution killed with signal 8 |
| 32 |
Runtime error |
679 ms |
294740 KB |
Execution killed with signal 11 |
