Submission #511174

#	Time	Username	Problem	Language	Result	Execution time	Memory
511174		600Mihnea	Mecho (IOI09_mecho)	C++17	100 / 100	182 ms	16016 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;
        continue;
      }
      if (ch == 'D') {
        r2 = i;
        c2 = j;
        continue;
      }
      if (ch == 'H') {
        bees.push_back({i, j});
        continue;
      }
    }
  }
  ///cout << r2 << " " << c2 << "\n";
  vector<pair<int, int>> m;
  m.push_back({r1, c1});
  a[r1][c1] = 1;
  compute(dist_b, bees);
  ord.clear();
  a[r2][c2] = 1;
  compute(dist_m, m);

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

  while (low <= high) {
    int stay = (low + high) / 2;
    ///stay = 5;
  ///  stay = 1;
    ///stay = 3;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        ok[i][j] = 0;
      }
    }
    ok[r1][c1] = 1;
    queue<pair<int, int>> q;
    q.push({r1, c1});
    while (!q.empty()) {
      int r = q.front().first, c = q.front().second;
      q.pop();
      if (ok[r][c]) {
        for (int k = 0; k < 4; k++) {
          int rn = r + dr[k];
          int cn = c + dc[k];
          int the_dist = dist_m[r][c] + 1;
          if (ok[rn][cn] || a[rn][cn] == 0) continue;

          dist_m[rn][cn] = the_dist;
          ok[rn][cn] |= ((stay + the_dist / speed) < (dist_b[rn][cn] + (rn == r2 && cn == c2)));
          if (ok[rn][cn]) q.push({rn, cn});
        }
      }
    }
//    cout << " val = " << ok[r2][c2 - 1] << "\n";
 //   exit(0);
 if (0) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          if ((stay + (dist_m[i][j] + speed - 1) / speed) > INF / 10 && 0) {
            cout << "? ";
          } else {
            cout << (stay + (dist_m[i][j] + speed - 1) / speed) << " ";
          }
        } else {
          cout << "- ";
        }
        ///cout << ok[i][j] << " ";
      }
      cout << "\n";
    }
    cout << "\n";

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          if (dist_b[i][j] > INF / 10) {
            cout << "? ";
          } else {
            cout << dist_b[i][j] << " ";
          }
        } else {
          cout << "- ";
        }
        ///cout << ok[i][j] << " ";
      }
      cout << "\n";
    }

    exit(0);}
    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: 100 / 100