| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 27487 | 2017-07-13T07:25:24 Z | TAMREF | Tracks in the Snow (BOI13_tracks) | C++11 | 1999 ms | 595580 KB |
#include <bits/stdc++.h>
using namespace std;
const int mx=4002, ms=4000*4000+1;
vector<int> G[ms];
int rep[ms];
char F[4000][mx];
int ans=0, rt=1, d, n, m, g=1;
void bfs(){
memset(rep,0,sizeof(rep));
queue<int> node,dep;
node.push(rt);
dep.push(1);
for(;!node.empty();){
int now=node.front(), dnow=dep.front();
node.pop(); dep.pop();
if(rep[now]) continue;
rep[now]=1; d=max(d,dnow);
for(int u : G[now]){
if(!rep[u]){
node.push(u);
dep.push(dnow+1);
}
}
}
}
void input(){
scanf("%d %d\n",&n,&m);
for(int i=0;i<n;i++) fgets(F[i],mx,stdin);
}
void gennode(){
for(int now=0;now<n*m;++now){
if(rep[now]||F[now/m][now%m]=='.') continue;
queue<int> Q;
Q.push(now); rep[now]=g;
char cvar=F[now/m][now%m];
for(int p;!Q.empty();){
p=Q.front(); Q.pop();
rep[p]=g;
if(p%m<m-1){
int r=p+1;
char var=F[r/m][r%m];
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!='.'){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
if(p%m>0){
int r=p-1;
char var=F[r/m][r%m];
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!='.'){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
if(p/m<n-1){
int r=p+m;
char var=F[r/m][r%m];
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!='.'){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
if(p/m>0){
int r=p-m;
char var=F[r/m][r%m];
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!='.'){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
}
++g;
}
}
int main(){
input();
gennode();
/*
printf("%d\n",g);
for(int i=1;i<g;i++,puts("")) for(int x : G[i]) printf("%d ",x);
*/
bfs();
printf("%d\n",d);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 203 ms | 456444 KB | Output is correct |
| 2 | Correct | 89 ms | 455160 KB | Output is correct |
| 3 | Correct | 106 ms | 455160 KB | Output is correct |
| 4 | Correct | 113 ms | 455292 KB | Output is correct |
| 5 | Correct | 113 ms | 455420 KB | Output is correct |
| 6 | Correct | 113 ms | 455160 KB | Output is correct |
| 7 | Correct | 103 ms | 455160 KB | Output is correct |
| 8 | Correct | 116 ms | 455160 KB | Output is correct |
| 9 | Correct | 109 ms | 455160 KB | Output is correct |
| 10 | Correct | 123 ms | 455420 KB | Output is correct |
| 11 | Correct | 106 ms | 455160 KB | Output is correct |
| 12 | Correct | 133 ms | 455676 KB | Output is correct |
| 13 | Correct | 106 ms | 455420 KB | Output is correct |
| 14 | Correct | 119 ms | 455420 KB | Output is correct |
| 15 | Correct | 149 ms | 456444 KB | Output is correct |
| 16 | Correct | 149 ms | 456444 KB | Output is correct |
| 17 | Correct | 139 ms | 456316 KB | Output is correct |
| 18 | Correct | 96 ms | 455292 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 106 ms | 455292 KB | Output is correct |
| 2 | Correct | 266 ms | 461564 KB | Output is correct |
| 3 | Correct | 966 ms | 500732 KB | Output is correct |
| 4 | Correct | 303 ms | 463100 KB | Output is correct |
| 5 | Correct | 1999 ms | 595580 KB | Output is correct |
| 6 | Correct | 1483 ms | 476896 KB | Output is correct |
| 7 | Correct | 96 ms | 455292 KB | Output is correct |
| 8 | Correct | 109 ms | 455292 KB | Output is correct |
| 9 | Correct | 99 ms | 455420 KB | Output is correct |
| 10 | Correct | 89 ms | 455292 KB | Output is correct |
| 11 | Correct | 116 ms | 455292 KB | Output is correct |
| 12 | Correct | 96 ms | 455548 KB | Output is correct |
| 13 | Correct | 266 ms | 461564 KB | Output is correct |
| 14 | Correct | 209 ms | 458880 KB | Output is correct |
| 15 | Correct | 213 ms | 459644 KB | Output is correct |
| 16 | Correct | 156 ms | 458108 KB | Output is correct |
| 17 | Correct | 483 ms | 471676 KB | Output is correct |
| 18 | Correct | 563 ms | 472444 KB | Output is correct |
| 19 | Correct | 339 ms | 463100 KB | Output is correct |
| 20 | Correct | 316 ms | 465532 KB | Output is correct |
| 21 | Correct | 646 ms | 482300 KB | Output is correct |
| 22 | Correct | 1883 ms | 595580 KB | Output is correct |
| 23 | Correct | 846 ms | 486916 KB | Output is correct |
| 24 | Correct | 886 ms | 501884 KB | Output is correct |
| 25 | Correct | 1996 ms | 526332 KB | Output is correct |
| 26 | Correct | 776 ms | 455160 KB | Output is correct |
| 27 | Correct | 1053 ms | 455940 KB | Output is correct |
| 28 | Correct | 1503 ms | 476896 KB | Output is correct |
| 29 | Correct | 1236 ms | 468124 KB | Output is correct |
| 30 | Correct | 1203 ms | 464620 KB | Output is correct |
| 31 | Correct | 1866 ms | 506880 KB | Output is correct |
| 32 | Correct | 999 ms | 459944 KB | Output is correct |