Submission #501941

#	Time	Username	Problem	Language	Result	Execution time	Memory
501941		lorenzoferrari	Mecho (IOI09_mecho)	C++14	84 / 100	178 ms	6744 KiB

mecho

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

int32_t main() {
  int n, s;
  cin >> n >> s;
  vector<vector<char>> m(n, vector<char> (n));
  int xs, ys;
  int xe, ye;
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    cin >> m[i][j];
    if (m[i][j] == 'M') xs = i, ys = j;
    if (m[i][j] == 'D') xe = i, ye = j;
  }
  queue<pair<int, int>> Q;
  vector<vector<int>> d(n, vector<int> (n, 1e9));
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    if (m[i][j] == 'H') {
      d[i][j] = 0;
      Q.push({i, j});
    }
  }
  while (!Q.empty()) {
    auto [x, y] = Q.front();
    Q.pop();
    if (x     && (m[x-1][y  ] == 'G' || m[x-1][y  ] == 'M') && d[x-1][y  ] > d[x][y] + 1) d[x-1][y  ] = d[x][y] + 1, Q.push({x-1, y  });
    if (y     && (m[x  ][y-1] == 'G' || m[x  ][y-1] == 'M') && d[x  ][y-1] > d[x][y] + 1) d[x  ][y-1] = d[x][y] + 1, Q.push({x  , y-1});
    if (x<n-1 && (m[x+1][y  ] == 'G' || m[x+1][y  ] == 'M') && d[x+1][y  ] > d[x][y] + 1) d[x+1][y  ] = d[x][y] + 1, Q.push({x+1, y  });
    if (y<n-1 && (m[x  ][y+1] == 'G' || m[x  ][y+1] == 'M') && d[x  ][y+1] > d[x][y] + 1) d[x  ][y+1] = d[x][y] + 1, Q.push({x  , y+1});
  }
  auto psb = [&](int delay) {
    // bfs from mecho's location
    // it's possible iff dist_from_mecho[i][j]/s + delay < d[i][j]
    queue<pair<int, int>> Q;
    vector<vector<int>> dm(n, vector<int> (n, 1e9));
    Q.push({xs, ys});
    dm[xs][ys] = 0;
    while (!Q.empty()) {
      auto [x, y] = Q.front();
      Q.pop();
      if (x     && m[x-1][y  ] != 'T' && dm[x-1][y  ] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x-1][y  ]) dm[x-1][y  ] = dm[x][y] + 1, Q.push({x-1, y  });
      if (y     && m[x  ][y-1] != 'T' && dm[x  ][y-1] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x  ][y-1]) dm[x  ][y-1] = dm[x][y] + 1, Q.push({x  , y-1});
      if (x<n-1 && m[x+1][y  ] != 'T' && dm[x+1][y  ] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x+1][y  ]) dm[x+1][y  ] = dm[x][y] + 1, Q.push({x+1, y  });
      if (y<n-1 && m[x  ][y+1] != 'T' && dm[x  ][y+1] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x  ][y+1]) dm[x  ][y+1] = dm[x][y] + 1, Q.push({x  , y+1});
    }
    return dm[xe][ye] != 1e9;
  };
  int l = 0, r = d[xs][ys];
  while (r - l > 1) {
    int mid = (r + l) / 2;
    if (psb(mid))
      l = mid;
    else
      r = mid;
  }
  cout << l << "\n";
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:25:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     auto [x, y] = Q.front();
      |          ^
mecho.cpp: In lambda function:
mecho.cpp:40:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |       auto [x, y] = Q.front();
      |            ^
mecho.cpp: In function 'int32_t main()':
mecho.cpp:47:21: warning: 'ye' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     return dm[xe][ye] != 1e9;
      |                     ^
mecho.cpp:47:17: warning: 'xe' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     return dm[xe][ye] != 1e9;
      |                 ^
mecho.cpp:49:26: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   int l = 0, r = d[xs][ys];
      |                          ^
mecho.cpp:49:22: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   int l = 0, r = d[xs][ys];
      |                      ^

• Subtask 1: 84 / 100