제출 #511162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511162		600Mihnea	Mecho (IOI09_mecho)	C++17	30 / 100	157 ms	16660 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int n;
int speed;
int r1, c1;
int r2, c2;
int a[N][N];
int dist_m[N][N];
int dist_b[N][N];

vector<pair<int, int>> ord;

void compute(int dist[N][N], vector<pair<int, int>> init) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dist[i][j] = INF;
    }
  }

  queue<pair<int, int>> q;
  for (auto &it : init) {
    dist[it.first][it.second] = 0;
    q.push(it);
  }
  while (!q.empty()) {
    auto it = q.front();
    int r = it.first;
    int c = it.second;
    ord.push_back(it);
    q.pop();
    for (int k = 0; k < 4; k++) {
      int rn = r + dr[k];
      int cn = c + dc[k];
      if (a[rn][cn] && dist[rn][cn] == INF) {
        dist[rn][cn] = 1 + dist[r][c];
        q.push({rn, cn});
      }
    }
  }
}

int dist[N][N];
bool ok[N][N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

 /// freopen ("input", "r", stdin);

  cin >> n >> speed;

  vector<pair<int, int>> bees;

  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 1; j <= n; j++) {
      char ch = s[j - 1];
      if (ch == 'T') {
        a[i][j] = 0;
        continue;
      }
      if (ch == 'G') {
        a[i][j] = 1;
        continue;
      }
      if (ch == 'M') {
        r1 = i;
        c1 = j;
        a[i][j] = 1;
        continue;
      }
      if (ch == 'D') {
        r2 = i;
        c2 = j;
        a[i][j] = 1;
        continue;
      }
      if (ch == 'H') {
        bees.push_back({i, j});
        continue;
      }
    }
  }
  vector<pair<int, int>> m;
  m.push_back({r1, c1});
  compute(dist_b, bees);
  ord.clear();
  compute(dist_m, m);

  int low = 0, high = dist_b[r1][c1], sol = -1;

  while (low <= high) {
    int stay = (low + high) / 2;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        ok[i][j] = 0;
      }
    }
    ok[r1][c1] = 1;
    for (auto &it : ord) {
      if (ok[it.first][it.second]) {
        int r = it.first, c = it.second;
        for (int k = 0; k < 4; k++) {
          int rn = r + dr[k];
          int cn = c + dc[k];
          ok[rn][cn] |= (stay + (dist_m[rn][cn] + speed - 1) / speed <= dist_b[rn][cn]);
        }
      }
    }
    if (ok[r2][c2]) {
      sol = stay;
      low = stay + 1;
    } else {
      high = stay - 1;
    }
  }

  cout << sol << "\n";
  return 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int val = dist_m[i][j];
      if (val == INF) {
        cout << "- ";
      } else {
        cout << val << " ";
      }
    }
    cout << "\n";
  }

  return 0;
}

• Subtask 1: 30 / 100