Submission #1196071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196071		aykhn	Mecho (IOI09_mecho)	C++20	100 / 100	176 ms	6236 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 8e2 + 5;

int A[4] = {0, 0, 1, -1};
int B[4] = {1, -1, 0, 0};

int n, s;
string arr[MXN];

vector<vector<int>> bfs(vector<array<int, 2>> st, int bee = 0)
{
  vector<vector<int>> d(n, vector<int>(n, inf));
  queue<array<int, 2>> q;
  for (auto &[x, y] : st) q.push({x, y}), d[x][y] = 0;
  while (!q.empty())
  {
    int x = q.front()[0], y = q.front()[1];
    q.pop();
    for (int k = 0; k < 4; k++)
    {
      int x1 = x + A[k], y1 = y + B[k];
      if (min(x1, y1) < 0 || max(x1, y1) >= n || arr[x1][y1] == 'T' || d[x1][y1] <= d[x][y] + 1) continue;
      if (bee && arr[x1][y1] == 'D') continue;
      if (!bee && arr[x1][y1] == 'H') continue;
      d[x1][y1] = d[x][y] + 1;
      q.push({x1, y1});
    }
  }
  return d;
}

void _()
{
  cin >> n >> s;
  for (int i = 0; i < n; i++) cin >> arr[i];
  array<int, 2> M, D;
  vector<array<int, 2>> H;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (arr[i][j] == 'M') M = {i, j};
      if (arr[i][j] == 'H') H.push_back({i, j});
      if (arr[i][j] == 'D') D = {i, j};
    }
  }
  auto hd = bfs(H, 1);
  int l = -1, r = hd[M[0]][M[1]] - 1;
  while (l < r)
  {
    int mid = (l + r + 1) >> 1;
    vector<vector<int>> d(n, vector<int>(n, inf));
    queue<array<int, 2>> q;
    d[M[0]][M[1]] = 0;
    q.push(M);
    while (!q.empty())
    {
      auto [x, y] = q.front();
      q.pop();
      for (int k = 0; k < 4; k++)
      {
        int x1 = x + A[k], y1 = y + B[k];
        if (min(x1, y1) < 0 || max(x1, y1) >= n || arr[x1][y1] == 'T' || d[x1][y1] <= d[x][y] + 1) continue;
        if ((d[x][y] + 1) / s + mid >= hd[x1][y1]) continue;
        d[x1][y1] = d[x][y] + 1;
        q.push({x1, y1});
      }
    }
    if (d[D[0]][D[1]] != inf) l = mid;
    else r = mid - 1;
  }
  cout << l << '\n';
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

• Subtask 1: 100 / 100