Submission #1079750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079750		juicy	Mecho (IOI09_mecho)	C++17	38 / 100	74 ms	9816 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

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

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);  

  int n, k; cin >> n >> k;
  vector a(n, vector<char>(n));
  vector ma(n, vector<int>(n, -1)), d(n, vector<int>(n, -1)), c(n, vector<int>(n, -1));
  queue<array<int, 2>> q;
  array<int, 2> s{}, t{};
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
      if (a[i][j] == 'H') {
        q.push({i, j});
        d[i][j] = 0;
      } else if (a[i][j] == 'M') {
        s = {i, j};
      } else if (a[i][j] == 'D') {
        t = {i, j};
      }
    }
  }
  auto inside = [&](int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < n;
  };
  auto bfs = [&](vector<vector<int>> &d) {
    while (q.size()) {
      auto [i, j] = q.front(); q.pop();
      for (int dr = 0; dr < 4; ++dr) {
        int u = i + dx[dr], v = j + dy[dr];
        if (inside(u, v) && a[u][v] != 'T' && a[u][v] != 'H' && d[u][v] == -1) {
          d[u][v] = d[i][j] + 1;
          q.push({u, v});
        }
      }
    } 
  };
  bfs(d);
  c[s[0]][s[1]] = 0;
  q.push(s);
  bfs(c);
  ma[s[0]][s[1]] = 1e9;
  q.push(s);
  d[t[0]][t[1]] = 1e9;
  vector vis(n, vector<bool>(n));
  vis[s[0]][s[1]] = 1;
  while (q.size()) {
    auto [i, j] = q.front(); q.pop();
    ma[i][j] = max(-1, min(ma[i][j], d[i][j] - (c[i][j] + k - 1) / k));
    for (int dr = 0; dr < 4; ++dr) {
      int u = i + dx[dr], v = j + dy[dr];
      if (inside(u, v) && a[u][v] != 'T' && a[u][v] != 'H' && c[u][v] == c[i][j] + 1) {
        ma[u][v] = max(ma[u][v], ma[i][j]);
        if (!vis[u][v]) {
          q.push({u, v});
          vis[u][v] = 1;
        }
      }
    }
  } 
  cout << ma[t[0]][t[1]];
  return 0;
}

• Subtask 1: 38 / 100