#include<bits/stdc++.h>
#define maxn 4002
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int tab[maxn][maxn],rep[maxn][maxn],prof[maxn][maxn],marc[maxn][maxn];
int resp,n,m;
deque<pair<int ,int> > nv;
int find(int x,int y){
//cout<<'1';
int r=rep[x][y];
if(r==m*x+y) return r;
int ry=r%m;
int rx=r/m;
return rep[x][y]=find(rx,ry);
}
void une(int x1,int y1,int x2,int y2){
//cout<<'2';
int r1=find(x1,y1);
x1=r1/m;y1=r1%m;
int r2=find(x2,y2);
x2=r2/m;y2=r2%m;
if(r1==r2) return;
if(prof[x1][y1]<prof[x2][y2]){
rep[x1][y1]=r2;
return;
}
rep[x2][y2]=r1;
if(prof[x1][y1]==prof[x2][y2]) prof[x1][y1]++;
}
void comp(int x,int y,int t){
//cout<<x<<ends<<y<<endl;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx==n||nx==-1||ny==m||ny==-1) continue;
if(tab[nx][ny]==(3-t)&&find(nx,ny)!=find(0,0)){
nv.push_back(make_pair(nx,ny));
}
if(tab[nx][ny]==t&&find(nx,ny)!=find(x,y)){
une(nx,ny,x,y);
comp(nx,ny,t);
}
}
}
void perc(int t){
//cout<<nv.size()<<endl;
resp++;
int s=nv.size();
for(int i=0;i<s;i++){
int a=(nv.front()).first,b=(nv.front()).second;
nv.pop_front();
//cout<<a<<ends<<b<<endl;
if(marc[a][b]==1) continue;
marc[a][b]=1;
comp(a,b,t);
une(a,b,0,0);
}
if(nv.size()==0) return;
perc(3-t);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char c;
scanf(" %c",&c);
if(c=='F') tab[i][j]=1;
else if(c=='R') tab[i][j]=2;
else tab[i][j]=0;
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<tab[i][j]<<ends;
}
cout<<endl;
}*/
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
rep[i][j]=m*i+j;
prof[i][j]=1;
}
}
nv.push_back(make_pair(0,0));
perc(tab[0][0]);
cout<<resp;
}
Compilation message
tracks.cpp: In function 'int main()':
tracks.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
tracks.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
12252 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
51 ms |
12536 KB |
Output is correct |
| 5 |
Correct |
16 ms |
6264 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 10 |
Correct |
15 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
15 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
35 ms |
6520 KB |
Output is correct |
| 13 |
Correct |
16 ms |
6256 KB |
Output is correct |
| 14 |
Correct |
16 ms |
6264 KB |
Output is correct |
| 15 |
Correct |
74 ms |
12152 KB |
Output is correct |
| 16 |
Correct |
92 ms |
12256 KB |
Output is correct |
| 17 |
Correct |
51 ms |
11768 KB |
Output is correct |
| 18 |
Correct |
52 ms |
12536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
57368 KB |
Output is correct |
| 2 |
Correct |
283 ms |
41652 KB |
Output is correct |
| 3 |
Correct |
1749 ms |
219836 KB |
Output is correct |
| 4 |
Correct |
439 ms |
88372 KB |
Output is correct |
| 5 |
Correct |
1046 ms |
171412 KB |
Output is correct |
| 6 |
Execution timed out |
2086 ms |
311480 KB |
Time limit exceeded |
| 7 |
Correct |
55 ms |
59868 KB |
Output is correct |
| 8 |
Correct |
54 ms |
57308 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1784 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1188 KB |
Output is correct |
| 11 |
Correct |
51 ms |
56864 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3064 KB |
Output is correct |
| 13 |
Correct |
280 ms |
41848 KB |
Output is correct |
| 14 |
Correct |
175 ms |
27384 KB |
Output is correct |
| 15 |
Correct |
136 ms |
32248 KB |
Output is correct |
| 16 |
Correct |
135 ms |
15956 KB |
Output is correct |
| 17 |
Correct |
692 ms |
87340 KB |
Output is correct |
| 18 |
Correct |
537 ms |
95380 KB |
Output is correct |
| 19 |
Correct |
435 ms |
88560 KB |
Output is correct |
| 20 |
Correct |
411 ms |
72696 KB |
Output is correct |
| 21 |
Correct |
1054 ms |
168060 KB |
Output is correct |
| 22 |
Correct |
1060 ms |
171484 KB |
Output is correct |
| 23 |
Correct |
1323 ms |
141200 KB |
Output is correct |
| 24 |
Correct |
940 ms |
165124 KB |
Output is correct |
| 25 |
Execution timed out |
2037 ms |
251908 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2119 ms |
782984 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2083 ms |
540180 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2087 ms |
312068 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2095 ms |
320556 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2095 ms |
316328 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2082 ms |
183320 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2128 ms |
638248 KB |
Time limit exceeded |
