제출 #1286051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286051		lucaskojima	Mecho (IOI09_mecho)	C++17	100 / 100	548 ms	6788 KiB

mecho

#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

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

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, x; cin >> n >> x;
  vector<string> ma(n); for (auto &x : ma) cin >> x;

  vector<pii> h;
  pii s, t;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (ma[i][j] == 'M')
        s = {i, j};
      else if (ma[i][j] == 'D')
        t = {i, j};
      else if (ma[i][j] == 'H')
        h.push_back({i, j});

  auto val = [&](int i, int j) -> bool {
    return 0 <= i && i < n && 0 <= j && j < n && (ma[i][j] == 'G' || ma[i][j] == 'M');
  };
  auto val_time = [&](int a, int b) -> bool {
    return a / x < b;
  };

  auto check = [&](int k) -> bool {
    vector bees_vis(n, vector<bool>(n));
    vector mecho_vis(n, vector<bool>(n));
    vector bees_time(n, vector<int>(n));
    vector mecho_time(n, vector<int>(n));
    queue<pii> q;

    for (auto [i, j] : h) {
      q.push({i, j});
      bees_vis[i][j] = true;
    }

    while (!q.empty()) {
      auto [x, y] = q.front(); q.pop();

      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (val(nx, ny) && !bees_vis[nx][ny]) {
          q.push({nx, ny});
          bees_vis[nx][ny] = true;
          bees_time[nx][ny] = bees_time[x][y] + 1;
        }
      }
    }

    q.push(s);
    mecho_vis[s.first][s.second] = true;
    if (bees_time[s.first][s.second] <= k) q.pop();

    while (!q.empty()) {
      auto [x, y] = q.front(); q.pop();

      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (val(nx, ny) && !mecho_vis[nx][ny] && val_time(mecho_time[x][y] + 1, bees_time[nx][ny] - k)) {
          q.push({nx, ny});
          mecho_vis[nx][ny] = true;
          mecho_time[nx][ny] = mecho_time[x][y] + 1;
        }
      }
    }

    bool ok = false;
    for (int i = 0; i < 4; i++) {
      int nx = t.first + dx[i];
      int ny = t.second + dy[i];
      if (val(nx, ny) && mecho_vis[nx][ny] && val_time(mecho_time[nx][ny], bees_time[nx][ny] - k))
        ok = true;
    }

    return ok;
  };

  int l = -1;    // l is good
  int r = n * n; // r is bad
  while (r > l + 1) {
    int m = (l + r) / 2;
    check(m) ? l = m : r = m;
  }

  cout << l << nl;
  return 0;
}

• Subtask 1: 100 / 100