Submission #1112365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112365		greenbinjack	Mecho (IOI09_mecho)	C++17	100 / 100	176 ms	6376 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define all(V) V.begin(), V.end()
#define x first
#define y second

using LL = long long;

const int N = 808;

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

char grid[N][N];  
int n, k, bees[N][N];
pair <int, int> start, finish;

bool valid (int i, int j) {
  return (i > 0 and i <= n and j > 0 and j <= n);
}

bool check (int Time) {
  if (bees[start.x][start.y] <= Time) return false;

  queue < pair <int, int> > q;
  q.push (start);
  vector < vector <int> > dist (n + 1, vector <int> (n + 1, INT_MAX));
  dist[start.x][start.y] = 0;
  while (!q.empty ()) {
    auto [X, Y] = q.front ();
    q.pop ();
    // if (finish == make_pair (X, Y)) break;
    for (int i = 0; i < 4; i++) {
      int nwX = X + dx[i], nwY = Y + dy[i];
      if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'D')) {
        if ((dist[X][Y] + 1) / k < bees[nwX][nwY] - Time and dist[X][Y] + 1 < dist[nwX][nwY]) {
          dist[nwX][nwY] = dist[X][Y] + 1;
          q.push ({nwX, nwY});
        }
      }
    }
  }
  return dist[finish.x][finish.y] != INT_MAX;
}

int main() {
  cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> grid[i][j];
      if (grid[i][j] == 'M') start = {i, j};
      if (grid[i][j] == 'D') finish = {i, j};
    }
  }
  
  queue < pair <int, int> > q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (grid[i][j] == 'H') {
        q.push ({i, j});
        bees[i][j] = 0;
      } else {
        bees[i][j] = INT_MAX;
      }
    }
  }

  while (!q.empty ()) {
    auto [X, Y] = q.front ();
    q.pop ();
    for (int i = 0; i < 4; i++) {
      int nwX = X + dx[i], nwY = Y + dy[i];
      if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'M') and bees[X][Y] + 1 < bees[nwX][nwY]) {
        bees[nwX][nwY] = bees[X][Y] + 1;
        q.push ({nwX, nwY});
      }
    }
  }

  int left = 0, right = n * n;
  while (left < right) {
    int mid = (left + right + 1) >> 1;
    if (check (mid)) left = mid;  
    else right = mid - 1;
  }

  if (!check (left)) left--;

  cout << left << '\n';

  return 0;
}

• Subtask 1: 100 / 100