제출 #1079773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079773		juicy	Mecho (IOI09_mecho)	C++17	100 / 100	154 ms	6840 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 d(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;
  };
  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] != 'D' && d[u][v] == -1) {
        d[u][v] = d[i][j] + 1;
        q.push({u, v});
      }
    }
  } 
  auto check = [&](int md) -> bool {
    vector c(n, vector<int>(n, -1));
    queue<array<int, 2>>().swap(q);
    q.push(s);
    c[s[0]][s[1]] = 0;
    while (q.size()) {
      auto [i, j] = q.front(); q.pop();
      if (tie(i, j) == tie(t[0], t[1])) {
        return 1;
      }
      if (md + c[i][j] / k >= d[i][j]) {
        continue;
      }
      for (int dr = 0; dr < 4; ++dr) {
        int u = i + dx[dr], v = j + dy[dr];
        if (inside(u, v) && a[u][v] != 'T' && c[u][v] == -1) {
          c[u][v] = c[i][j] + 1; 
          q.push({u, v});
        }
      }
    }
    return 0;
  };
  int l = 0, r = n * n, res = -1;
  while (l <= r) {
    int md = (l + r) / 2;
    if (check(md)) {
      res = md;
      l = md + 1;
    } else {
      r = md - 1;
    }
  } 
  cout << res;
  return 0;
}

• Subtask 1: 100 / 100