Submission #494914

#	Time	Username	Problem	Language	Result	Execution time	Memory
494914		Christopher_	Mecho (IOI09_mecho)	C++17	64 / 100	626 ms	17496 KiB

mecho

#include <bits/stdc++.h>

using namespace std;


#define int long long

#define ar array

const int mxN = 800;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int n, K;
vector<string> g(mxN);
pair<int,int> mecho, home;
vector<pair<int,int>> hives;
vector<vector<int>> disthives(mxN, vector<int>(mxN, (int) 1e7)), dist(mxN, vector<int>(mxN, (int) 1e7));

bool checkhives(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 'G' && disthives[x][y] == (int) 1e7;
}

bool checkbeer(int DIST, int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < n && g[x][y] != 'T' && g[x][y] != 'H' && disthives[x][y] > DIST && dist[x][y] == (int) 1e7;
}

void bfs(int m) {
  priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> pq;
  pq.push({m, mecho.first, mecho.second});
  while (!pq.empty()) {
    int d = pq.top()[0], x = pq.top()[1], y = pq.top()[2]; pq.pop();
    if (dist[x][y] < d) {
      continue;
    }
    for (int k = 0; k < 4; ++k) {
      int nx = x + dx[k], ny = y + dy[k];
      int DIST = (d + 1) / K;
      // if ((d + 1) % K) {
      //   ++DIST;
      // }
      if (checkbeer(DIST, nx, ny)) {
        pq.push({d + 1, nx, ny});
        dist[nx][ny] = d + 1;
      }
    }
  }
  // cout << dist[home.first][home.second] << '\n';
  // for (int i = 0; i < n; ++i) {
  //   for (int j = 0; j < n; ++j) {
  //     cout << dist[i][j] << ' ';
  //   }
  //   cout << '\n';
  // }
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> K;
  for (int i = 0; i < n; ++i) {
    cin >> g[i];
    for (int j = 0; j < n; ++j) {
      if (g[i][j] == 'M') {
        mecho = {i, j};
      } else if (g[i][j] == 'D') {
        home = {i, j};
      } else if (g[i][j] == 'H') {
        hives.push_back({i, j});
        disthives[i][j] = 0;
      }
    }
  }
  priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> pq;
  for (auto i : hives) {
    pq.push({0, i.first, i.second});
  }
  while (!pq.empty()) {
    int d = pq.top()[0], x = pq.top()[1], y = pq.top()[2]; pq.pop();
    if (disthives[x][y] < d) {
      continue;
    }
    for (int k = 0; k < 4; ++k) {
      int nx = x + dx[k], ny = y + dy[k];
      if (checkhives(nx, ny)) {
        pq.push({d + 1, nx, ny});
        disthives[nx][ny] = d + 1;
      }
    }
  }

  // for (int i = 0; i < n; ++i) {
  //   for (int j = 0; j < n; ++j) {
  //     cout << disthives[i][j] << ' ';
  //   }
  //   cout << '\n';
  // }

  // cerr << "HELLO\n";

  int l = 0, r = mxN * mxN;
  while (l <= r) {
    int m = (l + r) >> 1;
    dist = vector<vector<int>>(mxN, vector<int>(mxN, (int) 1e7));
    dist[mecho.first][mecho.second] = m * K;
    bfs(m * K);
    if (dist[home.first][home.second] < 1e7) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  cout << l - 1 << '\n';
}

• Subtask 1: 64 / 100