Submission #952038

#	Time	Username	Problem	Language	Result	Execution time	Memory
952038		Yell0	Mecho (IOI09_mecho)	C++17	100 / 100	117 ms	9308 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
const int MN=802;
int N, S, bee[MN][MN], best[MN][MN], dist[MN][MN];
char gr[MN][MN];
pii start, dest;

bool chk(int r, int c) {
  return 0 <= r && r < N && 0 <= c && c < N && gr[r][c] != 'T' && gr[r][c] != 'H';
}

bool bschk(int wait) {
  queue<pii> q;
  q.emplace(start);
  dist[start.first][start.second] = 0;
  if(wait > bee[start.first][start.second]) return 0;
  while(!q.empty()) {
    int r = q.front().first, c = q.front().second;
    q.pop();
    int d = dist[r][c] + 1;
    if(chk(r+1,c) && dist[r+1][c] == -1 && bee[r+1][c] - d/S - wait > -1) {
      dist[r+1][c] = d;
      q.emplace(r+1, c);
    }
    if(chk(r-1,c) && dist[r-1][c] == -1 && bee[r-1][c] - d/S - wait > -1) {
      dist[r-1][c] = d;
      q.emplace(r-1, c);
    }
    if(chk(r,c+1) && dist[r][c+1] == -1 && bee[r][c+1] - d/S - wait > -1) {
      dist[r][c+1] = d;
      q.emplace(r, c+1);
    }
    if(chk(r,c-1) && dist[r][c-1] == -1 && bee[r][c-1] - d/S - wait > -1) {
      dist[r][c-1] = d;
      q.emplace(r, c-1);
    }
  }

  return dist[dest.first][dest.second] > -1;
}
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin>>N>>S;
  queue<pii> beeq;
  for(int i=0; i<N; ++i) {
    cin>>gr[i];
    for(int j=0; j<N; ++j) {
      if(gr[i][j] == 'H') beeq.emplace(i,j);
      if(gr[i][j] == 'M') start = pii(i,j);
      if(gr[i][j] == 'D') dest = pii(i,j);
    }
  }

  memset(bee, -1, sizeof(bee));
  while(!beeq.empty()) {
    int r = beeq.front().first, c = beeq.front().second;
    beeq.pop();
    int dist = bee[r][c];
    if(chk(r+1,c) && bee[r+1][c] == -1 && gr[r+1][c] != 'D') {
      bee[r+1][c] = dist+1;
      beeq.emplace(r+1, c);
    }
    if(chk(r-1,c) && bee[r-1][c] == -1 && gr[r-1][c] != 'D') {
      bee[r-1][c] = dist+1;
      beeq.emplace(r-1, c);
    }
    if(chk(r,c+1) && bee[r][c+1] == -1 && gr[r][c+1] != 'D') {
      bee[r][c+1] = dist+1;
      beeq.emplace(r, c+1);
    }
    if(chk(r,c-1) && bee[r][c-1] == -1 && gr[r][c-1] != 'D') {
      bee[r][c-1] = dist+1;
      beeq.emplace(r, c-1);
    }
  }
  bee[dest.first][dest.second] = 1e9;

  int lo = 0, hi = N*N, ans = -1;
  while(lo <= hi) {
    int mid = (lo+hi)/2;
    memset(dist, -1, sizeof(dist));
    if(bschk(mid)) {
      ans = mid;
      lo = mid+1;
    } else hi = mid-1;
  }
  
  cout<<ans<<'\n';
  return 0;
}

• Subtask 1: 100 / 100