Submission #1099530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099530		sqrteipi	Mecho (IOI09_mecho)	C++14	88 / 100	399 ms	15596 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define int long long
char grid[805][805];
bool vis[805][805];
int ti[805][805], dist[805][805];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int32_t main() {
  int n, k;
  cin >> n >> k;
  pair<int, int> st, ed;
  for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
    cin >> grid[i][j];
    if (grid[i][j] == 'M') st = {i, j};
    if (grid[i][j] == 'D') ed = {i, j};
  }
  queue<array<int, 3>> q;
  for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (grid[i][j] == 'H') q.push({i, j, 0});
  while (!q.empty()) {
    auto [x, y, d] = q.front(); q.pop();
    if (0 <= x && x < n && 0 <= y && y < n && !vis[x][y] && grid[x][y] != 'T' && grid[x][y] != 'D') {
      vis[x][y] = true; ti[x][y] = d;
      for (int i=0; i<4; i++) q.push({x + dx[i], y + dy[i], d + 1});
    }
  }
  int l=0, r=1e9, bst = -1;
  while (l <= r) {
    int m = (l + r) / 2;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) vis[i][j] = dist[i][j] = 0;
    q.push({st.first, st.second, m}); 
    while (!q.empty()) {
      auto [x, y, d] = q.front(); q.pop();
      if (0 <= x && x < n && 0 <= y && y < n && !vis[x][y] && grid[x][y] != 'T' && (d / k < ti[x][y] || grid[x][y] == 'D')) {
        vis[x][y] = true; dist[x][y] = d;
        for (int i=0; i<4; i++) q.push({x + dx[i], y + dy[i], d + 1});
      }
    }
    if (vis[ed.first][ed.second]) l = m + 1, bst = max(bst, m);
    else r = m - 1;
  }
  cout << bst / k;
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:21:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     auto [x, y, d] = q.front(); q.pop();
      |          ^
mecho.cpp:30:76: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   30 |     for (int i=0; i<n; i++) for (int j=0; j<n; j++) vis[i][j] = dist[i][j] = 0;
      |                                                                 ~~~~~~~~~~~^~~
mecho.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |       auto [x, y, d] = q.front(); q.pop();
      |            ^

• Subtask 1: 88 / 100