Submission #652788

#	Time	Username	Problem	Language	Result	Execution time	Memory
652788		chanhchuong123	Mecho (IOI09_mecho)	C++14	Compilation error	0 ms	0 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;
}

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 (check(0) == 0) {
    cout << "-1";
    return 0;
  }
  int l = 0, r = n * n + n;
  while (r - l > 1) {
    int mid = l + r >> 1;

    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});
        }
      }
    }

    bool ok = false;
    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)) ok = true;
    }
    if (ok) l = mid;
    else r = mid;
  }
  cout << l;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:51:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     auto [u, v] = q.front();
      |          ^
mecho.cpp:62:7: error: 'check' was not declared in this scope
   62 |   if (check(0) == 0) {
      |       ^~~~~
mecho.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = l + r >> 1;
      |               ~~^~~
mecho.cpp:79:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |       auto [u, v] = q.front();
      |            ^