Submission #264668

#	Time	Username	Problem	Language	Result	Execution time	Memory
264668		WLZ	Mecho (IOI09_mecho)	C++14	38 / 100	1064 ms	7188 KiB

mecho

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

const int INF = 0x3f3f3f3f;
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> > q;
  vector< vector<int> > dist1(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') {
        mr = i; mc = j;
      } else if (grid[i][j] == 'H') {
        q.push({i, j});
        dist1[i][j] = 0;
      } else if (grid[i][j] == 'D') {
        dr = i; dc = j;
      }
    }
  }
  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] != -1) {
        continue;
      }
      dist1[nr][nc] = dist1[r][c] + s;
      q.push({nr, nc});
    }
  }
  int lo = 0, hi = n * n, ans = -1;
  for (int i = 0; i < 50; i++) {
    int mid = (lo + hi + 1) / 2;
    //cout << mid << endl;
    vector< vector<int> > dist2(n, vector<int>(n, INF));
    dist2[mr][mc] = s * mid;
    if (dist2[mr][mc] >= dist1[mr][mc]) {
      hi = mid - 1;
      continue;
    }
    q.push({mr, mc});
    while (!q.empty()) {
      int r = q.front().first, c = q.front().second;
      //cout << r << ' ' << c << endl;
      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 || dist2[r][c] + 1 >= dist2[nr][nc] || (!(nr != dr && nc != dc) && dist2[r][c] + 1 >= dist1[nr][nc]) || grid[nr][nc] == 'T') {
          continue;
        }
        dist2[nr][nc] = dist2[r][c] + 1;
        q.push({nr, nc});
      }
    }
    if (dist2[dr][dc] <= dist1[dr][dc]) {
      ans = mid;
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:47:17: warning: 'mc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     dist2[mr][mc] = s * mid;
      |                 ^
mecho.cpp:47:13: warning: 'mr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     dist2[mr][mc] = s * mid;
      |             ^
mecho.cpp:66:21: warning: 'dc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if (dist2[dr][dc] <= dist1[dr][dc]) {
      |                     ^
mecho.cpp:66:17: warning: 'dr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if (dist2[dr][dc] <= dist1[dr][dc]) {
      |                 ^

• Subtask 1: 38 / 100