Submission #652789

#	Time	Username	Problem	Language	Result	Execution time	Memory
652789		chanhchuong123	Mecho (IOI09_mecho)	C++14	85 / 100	157 ms	6252 KiB

mecho

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int N = 802;
int n, S;
char a[N][N];

int bee[N][N];
int dis[N][N];
pair<int, int> s, t;
queue<pair<int, int>> q;

bool in(int x, int y) {
  return (1 <= x && x <= n) && (1 <= y && y <= n) && (a[x][y] == 'G' || a[x][y] == 'M');
}

bool canMove(int mocho, int bee) {
  return mocho / S < bee;
}

bool ok(int mid) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
        dis[i][j] = 1e9;
    }

    q.push(s); dis[s.fi][s.se] = 0;
    if (bee[s.fi][s.se] <= mid) q.pop();

    while (q.size()) {
      auto [u, v] = q.front();
      q.pop();
      for (int i = 0; i < 4; i++) {
        int x = u + dx[i], y = v + dy[i];
        if (in(x, y) && dis[x][y] == 1e9 &&
            canMove(dis[u][v] + 1, bee[u][v] - mid)) {
          dis[x][y] = dis[u][v] + 1;
          q.push({x, y});
        }
      }
    }

    for (int i = 0; i < 4; i++) {
      int x = t.fi + dx[i], y = t.se + dy[i];
      if (in(x, y) && dis[x][y] != 1e9 &&
      canMove(dis[x][y], bee[x][y] - mid))
        return true;
    }

    return false;
}

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

  cin >> n >> S;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++)
      bee[i][j] = 1e9;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == 'M')
        s = make_pair(i, j);
      if (a[i][j] == 'D')
        t = make_pair(i, j);
      if (a[i][j] == 'H') {
        bee[i][j] = 0;
        q.push({i, j});
      }
    }
  }

  while (q.size()) {
    auto [u, v] = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
      int x = u + dx[i], y = v + dy[i];
      if (in(x, y) && bee[x][y] == 1e9) {
        q.push({x, y});
        bee[x][y] = bee[u][v] + 1;
      }
    }
  }

  if (ok(0) == 0) {
    cout << "-1";
    return 0;
  }
  int l = 0, r = n * n + n;
  while (r - l > 1) {
    int mid = l + r >> 1;
    if (ok(mid)) l = mid;
    else r = mid;
  }
  cout << l;
}

Compilation message (stderr)

mecho.cpp: In function 'bool ok(int)':
mecho.cpp:37:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |       auto [u, v] = q.front();
      |            ^
mecho.cpp: In function 'int main()':
mecho.cpp:83:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     auto [u, v] = q.front();
      |          ^
mecho.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 85 / 100