Submission #1088632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088632		v_matei	Mecho (IOI09_mecho)	C++17	31 / 100	209 ms	26676 KiB

mecho

#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");

#define NMAX 1000
#define INF INT_MAX

int n, s;
char map[NMAX][NMAX];
pii start, finish;
std::vector<pii> hives;
std::vector<std::vector<int>> d1(NMAX, std::vector<int>(NMAX, INF)),
    d2(NMAX, std::vector<int>(NMAX, INF));

int di[]{1, -1, 0, 0}, dj[]{0, 0, 1, -1};

void citire() {
  std::cin >> n >> s;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      std::cin >> map[i][j];
      if (map[i][j] == 'M')
        start = {i, j};
      if (map[i][j] == 'D')
        finish = {i, j};
      if (map[i][j] == 'H')
        hives.push_back({i, j});
    }
}

bool in(pii coord) {
  int i = coord.first, j = coord.second;
  return i >= 0 && i < n && j >= 0 && j < n;
}

void bfs(std::queue<pii> &q, std::vector<std::vector<int>> &d,
         std::function<bool(pii coords)> check) {
  while (!q.empty()) {
    pii u = q.front();
    int i = u.first;
    int j = u.second;
    q.pop();

    for (int k = 0; k < 4; k++) {
      int ni = i + di[k];
      int nj = j + dj[k];
      if (check({ni, nj}) && d[ni][nj] > d[i][j] + 1) {
        d[ni][nj] = d[i][j] + 1;
        q.push({ni, nj});
      }
    }
  }
}
void bfs2(std::queue<pii> &q, std::vector<std::vector<int>> &d,
          std::function<bool(pii coords)> check) {
  while (!q.empty()) {
    pii u = q.front();
    int i = u.first;
    int j = u.second;
    q.pop();

    for (int k = 0; k < 4; k++) {
      int ni = i + di[k];
      int nj = j + dj[k];
      if (check({ni, nj}) && d[ni][nj] > d[i][j] + 1) {
        if (d[i][j] + 1 < s * d2[ni][nj]) {
          d[ni][nj] = d[i][j] + 1;
          q.push({ni, nj});
        }
      }
    }
  }
}

int b_search(int l, int r, std::function<bool(int)> f) {
  while (r > l + 1) {
    int mid = (r + l) / 2;
    if (f(mid))
      l = mid;
    else
      r = mid;
  }
  return l;
}

int ok = 0;

int main() {
  std::cin.tie(0)->std::ios::sync_with_stdio(0);
  citire();

  std::queue<pii> q;

  for (pii it : hives) {
    q.push(it);
    d2[it.first][it.second] = 0;
  }

  bfs(q, d2, [&](pii coords) {
    return in(coords) && map[coords.first][coords.second] != 'D' &&
           map[coords.first][coords.second] != 'T';
  });
  int ans = b_search(0, n * n, [&](int w) {
    std::vector<std::vector<int>> d(NMAX, std::vector<int>(NMAX, INF));
    d[start.first][start.second] = w * s;
    q.push(start);
    if (w >= d2[start.first][start.second])
      q.pop();
    bfs2(q, d, [&](pii coords) {
      return in(coords) && map[coords.first][coords.second] != 'H' &&
             map[coords.first][coords.second] != 'T';
    });

    for (int k = 0; k < 4; k++) {
      if (d[finish.first+di[k]][finish.second+dj[k]] != INF) {
        ok = 1;
        return true;
      }
    }
    return false;
  });

  if (ok) {
    std::cout << ans << '\n';
  } else
    std::cout << -1 << '\n';
  /*for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (d2[i][j] != INF)
        std::cout << d2[i][j] << ' ';
      else
        std::cout << "oo ";
    }
    std::cout << '\n';
  }*/
  return 0;
}

• Subtask 1: 31 / 100