Submission #465153

#	Time	Username	Problem	Language	Result	Execution time	Memory
465153		MohamedFaresNebili	Mecho (IOI09_mecho)	C++14	100 / 100	267 ms	21696 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
  int nx[4]={1, -1, 0, 0}, ny[4]={0, 0, 1, -1};
  char grid[2000][2000]; bool vis[2000][2000];
  int d[2000][2000]; int n, s, sx, sy, hx, hy;
  bool bfs(int v)
  {
    if(v*s>=d[sx][sy]) return false;
    memset(vis, 0, sizeof vis); 
    deque<pair<int, pair<int, int>>>q;
    q.push_back(make_pair(v*s, make_pair(sx, sy)));
    vis[sx][sy]=true;
    while(!q.empty()) {
      int dis=q.front().first;
      int a=q.front().second.first, b=q.front().second.second;
      q.pop_front();
      if(grid[a][b]=='D') return true;
      for(int l=0;l<4;l++) {
        int x=a+nx[l], y=b+ny[l];
        if(x>=0&&x<n&&y>=0&&y<n) {
          if(grid[x][y]!='T'&&dis+1<d[x][y]&&!vis[x][y]) {
            q.push_back(make_pair(dis+1, make_pair(x, y))); 
            vis[x][y]=true;
          }
        }
      }
    }
    return false;
  }
int main()
{
  cin>>n>>s;
  deque<pair<int, int>>q;
  memset(d, -1, sizeof(d));
  for(int l=0;l<n;l++) {
    for(int i=0;i<n;i++) 
    {
      cin>>grid[l][i];
      if(grid[l][i]=='H') {
        q.push_back(make_pair(l, i));
        d[l][i]=0;
      }
      else if(grid[l][i]=='M') {
        sx=l; sy=i; grid[l][i]='G';
      }
      else if(grid[l][i]=='D') {
        hx=l; hy=i;
      }
    }
  }
  while(!q.empty()) {
    int a=q.front().first, b=q.front().second; q.pop_front();
    for(int l=0;l<4;l++) {
      int x=a+nx[l], y=b+ny[l];
      if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]=='G'&&d[x][y]==-1) {
        d[x][y]=d[a][b]+s; q.push_back(make_pair(x, y));
      }
    }
  }
  d[hx][hy]=n*n*s;
  int lo=-1, hi=2*n*n;
  while(hi-lo>1) {
    int mid=(hi+lo)/2;
    if(bfs(mid)) lo=mid;
    else hi=mid;
  }
  cout<<lo<<'\n';
  return 0;
}

• Subtask 1: 100 / 100