Submission #1180804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180804		nolqf	Mecho (IOI09_mecho)	C++20	30 / 100	139 ms	6416 KiB

mecho

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 8e2;
const int INF = 2e9;

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

string T[1 + MAXN];
int lim[1 + MAXN][1 + MAXN];
int dist[1 + MAXN][1 + MAXN];
int n, s, xs, ys, xd, yd;

bool out( int x, int y ) {
  return 1 > x || 1 > y || n < x || n < y;
}

bool check( int tt ) {
  for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= n; ++j ) {
      dist[i][j] = INF;
    }
  }
  queue<pair<int, int>> q;
  q.push({xs, ys});
  dist[xs][ys] = 0;
  while ( !q.empty() ) {
    auto [x, y] = q.front();
    if ( x == xd && y == yd ) {
      return true;
    }
    q.pop();
    int nd = (dist[x][y] + 1) / s + ((dist[x][y] + 1) % s != 0);
    for ( int d = 0; d < 4; ++d ) {
      int nx = x + dx[d], ny = y + dy[d];
      if ( !out(nx, ny) && lim[nx][ny] >= tt + nd && dist[nx][ny] == INF ) {
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny}); 
      }
    }
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> s;
  queue<pair<int, int>> q;
  for ( int i = 1; i <= n; ++i ) {
    cin >> T[i];
    T[i] = '#' + T[i];
    for ( int j = 1; j <= n; ++j ) {
      lim[i][j] = INF;
      dist[i][j] = INF;
      if ( T[i][j] == 'H' ) {
        q.push({i, j});
        lim[i][j] = 0;
      } else if ( T[i][j] == 'T' ) {
        lim[i][j] = 0;	       
      } else if ( T[i][j] == 'M' ) {
        xs = i, ys = j;
      } else if ( T[i][j] == 'D' ) {
        xd = i, yd = j;
      }
    }
  }
  while ( !q.empty() ) {
    auto [i, j] = q.front();
    q.pop();
    for ( int d = 0; d < 4; ++d ) {
      int ni = i + dx[d], nj = j + dy[d];
      if ( !out(ni, nj) && lim[ni][nj] == INF ) {
        lim[ni][nj] = lim[i][j] + 1;
        q.push({ni, nj});
      }
    }
  }
  int l = 0, r = lim[xs][ys];
  while ( r - l > 1 ) {
    int mid = (l + r) / 2;
    if ( check(mid) ) {
      l = mid;
    } else {
      r = mid;
    }
  }
  if ( !check(0) ) {
    cout << "-1\n";
    return 0;
  }
  cout << (check(r) ? r : l) << "\n";
  return 0;  
}

• Subtask 1: 30 / 100