Submission #264502

#	Time	Username	Problem	Language	Result	Execution time	Memory
264502		WLZ	Mecho (IOI09_mecho)	C++14	6 / 100	1079 ms	7160 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

const vector<int> dx = {0, 0, -1, 1};
const vector<int> dy = {1, -1, 0, 0};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, s;
  cin >> n >> s;
  vector<string> grid(n);
  queue< pair<int, int> > q1, q2;
  vector< vector<int> > dist1(n, vector<int>(n, -1)), dist2(n, vector<int>(n, -1));
  int mr, mc, dr, dc;
  for (int i = 0; i < n; i++) {
    cin >> grid[i];
    for (int j = 0; j < n; j++) {
      if (grid[i][j] == 'M') {
        q1.push({i, j});
        dist1[i][j] = 0;
        mr = i; mc = j;
      } else if (grid[i][j] == 'H') {
        q2.push({i, j});
        dist2[i][j] = 0;
      } else if (grid[i][j] == 'D') {
        dr = i; dc = j;
      }
    }
  }
  while (!q1.empty()) {
    int r = q1.front().first, c = q1.front().second;
    q1.pop();
    for (int k = 0; k < 4; k++) {
      int nr = r + dx[k], nc = c + dy[k];
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist1[nr][nc] != -1) {
        continue;
      }
      dist1[nr][nc] = dist1[r][c] + 1;
      q1.push({nr, nc});
    }
  }
  while (!q2.empty()) {
    int r = q2.front().first, c = q2.front().second;
    q2.pop();
    for (int k = 0; k < 4; k++) {
      int nr = r + dx[k], nc = c + dy[k];
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist2[nr][nc] != -1) {
        continue;
      }
      dist2[nr][nc] = dist2[r][c] + s;
      q2.push({nr, nc});
    }
  }
  int lo = 0, hi = n * n, ans = -1;
  for (int i = 0; i < 50; i++) {
    int mid = (lo + hi + 1) / 2;
    vector< vector<bool> > was(n, vector<bool>(n, false));
    queue< pair<int, int> > q;
    q.push({mr, mc});
    while (!q.empty()) {
      int r = q.front().first, c = q.front().second;
      q.pop();
      for (int k = 0; k < 4; k++) {
        int nr = r + dx[k], nc = c + dy[k];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist1[nr][nc] + 4 * mid > dist2[nr][nc] || was[nr][nc]) {
          continue;
        }
        was[nr][nc] = true;
        q.push({nr, nc});
      }
    }
    if (was[dr][dc]) {
      lo = mid;
      ans = mid;
    } else {
      hi = mid - 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:73:15: warning: 'dr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     if (was[dr][dc]) {
      |               ^

• Subtask 1: 6 / 100