Submission #131472

#	Time	Username	Problem	Language	Result	Execution time	Memory
131472		dragonslayerit	Mecho (IOI09_mecho)	C++14	100 / 100	271 ms	7832 KiB

mecho

#include <cstdio>
#include <queue>
#include <tuple>

const int INF=1e9+7;

const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};

char grid[1005][1005];
int danger[1005][1005];

int dist[1005][1005];
int N,S;

bool check(int start){
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      dist[x][y]=INF;
    }
  }
  std::queue<std::pair<int,int> > mecho;
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      if(grid[x][y]=='M'){
	dist[x][y]=0;
	mecho.push({x,y});
      }
    }
  }
  while(!mecho.empty()){
    int x,y;
    std::tie(x,y)=mecho.front();
    mecho.pop();
    if(dist[x][y]/S+start>=danger[x][y]) continue;
    if(grid[x][y]=='D') return true;
    for(int d=0;d<4;d++){
      int x2=x+dx[d],y2=y+dy[d];
      if((grid[x2][y2]=='G'||grid[x2][y2]=='D')&&dist[x2][y2]==INF){
	dist[x2][y2]=dist[x][y]+1;
	mecho.push({x2,y2});
      }
    }
  }
  return false;
}

int main(){
  scanf("%d %d",&N,&S);
  for(int x=0;x<N;x++){
    scanf("%s",grid[x]);
  }
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      danger[x][y]=INF;
    }
  }
  std::queue<std::pair<int,int> > bees;
  for(int x=0;x<N;x++){
    for(int y=0;y<N;y++){
      if(grid[x][y]=='H'){
	danger[x][y]=0;
	bees.push({x,y});
      }
    }
  }
  while(!bees.empty()){
    int x,y;
    std::tie(x,y)=bees.front();
    bees.pop();
    for(int d=0;d<4;d++){
      int x2=x+dx[d],y2=y+dy[d];
      if((grid[x2][y2]=='G'||grid[x2][y2]=='M')&&danger[x2][y2]==INF){
	danger[x2][y2]=danger[x][y]+1;
	bees.push({x2,y2});
      }
    }
  }
  int low=-1,high=N*N;
  while(high-low>1){
    int mid=(low+high)/2;
    if(check(mid)){
      low=mid;
    }else{
      high=mid;
    }
  }
  printf("%d\n",low);
  return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&S);
   ~~~~~^~~~~~~~~~~~~~~
mecho.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",grid[x]);
     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100