Submission #1140622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140622		limits	Mecho (IOI09_mecho)	C++20	100 / 100	370 ms	6516 KiB

mecho

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                         \
  {                                                                    \
    ++recur_depth;                                                     \
    auto x_ = x;                                                       \
    --recur_depth;                                                     \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"   \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl; \
  }
#else
#define dbg(x)
#endif
template <typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(
    Ostream& os, const Cont& v) {
  os << "[";
  for (auto& x : v) {
    os << x << ", ";
  }
  return os << "]";
}
template <typename Ostream, typename... Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
  return os << "{" << p.first << ", " << p.second << "}";
}
// === Debug macro ends here ===

#define f0r(i, k) for (int i = 0; i < (k); ++i)
#define fnr(i, n, k) for (int i = (n); i < (k); ++i)
#define r0f(i, k) for (int i = (k); i >= 0; --i)
#define rnf(i, n, k) for (int i = (n); i >= k; --i)
#define forl(i, l) for (auto i : l)
#define ctn(x) cout << x << '\n'
#define ctl(lst)                            \
  {                                         \
    for (auto& a : (lst)) cout << a << ' '; \
    cout << endl;                           \
  }
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(), (v).end()
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using pi = pair<int, int>;
using Adj = V<vi>;
using str = string;

int n, s;
pi dirs[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
V<str> grid;
bool check_cell(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < n &&
         (grid[x][y] == 'G' || grid[x][y] == 'M');
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> n >> s;
  grid.resize(n);
  forl(&v, grid) cin >> v;

  V<pi> hives;
  int mechoX, mechoY, homeX, homeY;
  f0r(i, n) {
    f0r(j, n) {
      if (grid[i][j] == 'M')
        mechoX = i, mechoY = j;
      else if (grid[i][j] == 'D')
        homeX = i, homeY = j;
      else if (grid[i][j] == 'H')
        hives.pb({i, j});
    }
  }
  dbg(hives);
  dbg(mechoX);
  dbg(mechoY);
  dbg(homeX);
  dbg(homeY);

  int l = 0, r = n * n;
  V<vi> mecho_time, bees_time;
  while (l <= r) {
    mecho_time.assign(n, vi(n, -1));
    bees_time.assign(n, vi(n, -1));

    int eat_time = (l + r) / 2;

    queue<pi> q;
    for (auto& [x, y] : hives) {
      q.push({x, y});
      bees_time[x][y] = 0;
    }

    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop();
      for (auto [dx, dy] : dirs) {
        int nx = x + dx, ny = y + dy;
        if (check_cell(nx, ny) && bees_time[nx][ny] == -1) {
          bees_time[nx][ny] = bees_time[x][y] + 1;
          q.push({nx, ny});
        }
      }
    }

    if (bees_time[mechoX][mechoY] > eat_time) q.push({mechoX, mechoY});
    mecho_time[mechoX][mechoY] = 0;
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop();
      for (auto [dx, dy] : dirs) {
        int nx = x + dx, ny = y + dy;
        if (check_cell(nx, ny) && mecho_time[nx][ny] == -1) {
          mecho_time[nx][ny] = mecho_time[x][y] + 1;
          if (mecho_time[nx][ny] / s < (bees_time[nx][ny] - eat_time)) {
            q.push({nx, ny});
          }
        }
      }
    }
    bool reached = false;
    for (auto [dx, dy] : dirs) {
      int nx = homeX + dx, ny = homeY + dy;
      if (check_cell(nx, ny) && (mecho_time[nx][ny] != -1) &&
          (mecho_time[nx][ny] / s < (bees_time[nx][ny] - eat_time))) {
        dbg("YESSS");
        reached = true;
      }
    }
    dbg(eat_time);
    dbg(bees_time);
    dbg(mecho_time);
    if (reached)
      l = eat_time + 1;
    else
      r = eat_time - 1;
  }
  ctn(l - 1);
}

• Subtask 1: 100 / 100