제출 #583474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583474		HeyYouNotYouYou	Mecho (IOI09_mecho)	C++14	100 / 100	270 ms	16572 KiB

mecho

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int n , o, srcx, srcy, destx, desty, ar[N][N],arr[N][N],arr2[N][N];
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
bool vis[N][N];
bool valid(int x, int y){
  if(x>=0 && x<n && y>=0 && y<n) return true;
  return false;
}

bool check(int mins)
{

  memset(vis,0,sizeof vis);
  memset(arr2,0,sizeof arr2);
  queue<pair<int,int>>qq;
  qq.push({srcx,srcy});
  vis[srcx][srcy]=1;
  if(arr[srcx][srcy]<=mins) return false;
  arr2[srcx][srcy]=0;
  while(!qq.empty()){
    int curx=qq.front().first;
    int cury=qq.front().second;
    qq.pop();
    for(int i = 0 ; i < 4; i ++)
    {
      int gox = curx+dx[i], goy = cury+dy[i];

      if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1){
        if(arr[gox][goy] > floor((double)(arr2[curx][cury]+1)/(double)o)+mins){
        //  cout<<curx<<" "<<cury<<" "<<gox<<" "<<goy<<" "<<arr2[curx][cury]<<" "<<arr[gox][goy]-mins<<" "<<c<<" "<<arr2[curx][cury]+(c%o==0&&c>0)<<endl;
          vis[gox][goy]=1;
          arr2[gox][goy]=arr2[curx][cury]+1;
          if(gox==destx&&goy==desty) return true;
          qq.push({gox,goy});
        }
      }
    }
  }


  return false;
}

void bfs(){
  queue<pair<int,int>>q;
  memset(vis,0,sizeof vis);
  for(int i = 0 ; i < n ; i ++)
    for(int j = 0 ; j < n ; j ++)
      {
        if(ar[i][j]==1){
          q.push({i,j});
          vis[i][j]=1;
          arr[i][j]=0;
        }
      }

  while(!q.empty())
  {
    int curx=q.front().first;
    int cury=q.front().second;
    q.pop();
    for(int i = 0 ; i < 4; i ++)
    {
      int gox = curx+dx[i], goy = cury+dy[i];
      if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1 && (destx!=gox || desty!=goy)){
        vis[gox][goy]=1;
        arr[gox][goy]=arr[curx][cury]+1;
        q.push({gox,goy});
      }
    }
  }

}


int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n >> o;
  for(int i = 0 ; i < n ; i ++){
    for(int j = 0 ; j < n ; j ++){
      char x; cin >> x;
      arr[i][j]=1e9;
      ar[i][j] = (x=='H'?1:((x=='G'||x=='D'||x=='M')?0:-1));
      if(x=='M') srcx=i, srcy=j;
      if(x=='D') destx=i, desty=j;
    }
  }
  bfs();
  int l = 0 , r = 1e9;
  int ans=-1;
  while(l <= r)
  {
    int mid = l + (r - l) / 2;;
  //  cout<<mid<<endl;
    if(check(mid))
    {
      l = mid+1;
      ans=mid;
    }
    else
    {
      r = mid-1;
    }
  }
  cout<<ans<<endl;
}

• Subtask 1: 100 / 100