This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
int map_size,civ;
int Q[4000010][2],front,rear;
int Q2[1000010][2],front2,rear2;
int start[100010][2];
int map[2010][2010],vis[100010];
int extend(int a,int x,int y)
{
if(x==0 || x==map_size+1 || y==0 || y==map_size+1) return 0;
if(map[x][y]!=0) return 0;
map[x][y]=a;
Q[rear][0]=x; Q[rear++][1]=y;
return 1;
}
void find(int x,int y)
{
if(map[x+1][y])
{
if(map[x][y]>map[x+1][y]) vis[map[x][y]]=vis[map[x+1][y]];
else vis[map[x+1][y]]=vis[map[x][y]];
}
if(map[x-1][y])
{
if(map[x][y]>map[x-1][y]) vis[map[x][y]]=vis[map[x-1][y]];
else vis[map[x-1][y]]=vis[map[x][y]];
}
if(map[x][y+1])
{
if(map[x][y]>map[x][y+1]) vis[map[x][y]]=vis[map[x][y+1]];
else vis[map[x][y+1]]=vis[map[x][y]];
}
if(map[x][y-1])
{
if(map[x][y]>map[x][y-1]) vis[map[x][y]]=vis[map[x][y-1]];
else vis[map[x][y-1]]=vis[map[x][y]];
}
}
void solve(int time)
{
int x,y,a;
int i;
int check=1;
for(i=1;i<=civ;i++) if(vis[i]!=1) check=0;
if(check) {printf("%d",time); return ;}
int j=rear;
while(front!=j)
{
x=Q[front][0]; y=Q[front++][1]; a=map[x][y];
if(extend(a,x+1,y)) find(x+1,y);
if(extend(a,x-1,y)) find(x-1,y);
if(extend(a,x,y+1)) find(x,y+1);
if(extend(a,x,y-1)) find(x,y-1);
}
for(i=1;i<=civ;i++) if(vis[i]==vis[vis[i]]) {vis[i]=vis[vis[i]];}
solve(time+1);
}
int main()
{
int i;
scanf("%d %d",&map_size,&civ);
for(i=1;i<=civ;i++) vis[i]=i;
for(i=1;i<=civ;i++)
{
scanf("%d %d",&start[i][0],&start[i][1]);
map[start[i][0]][start[i][1]]=i;
Q[rear][0]=start[i][0]; Q[rear++][1]=start[i][1];
find(start[i][0],start[i][1]);
}
solve(0);
return 0;
}
Compilation message (stderr)
civilization.cpp: In function 'int main()':
civilization.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&map_size,&civ);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
civilization.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&start[i][0],&start[i][1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |