Submission #1278590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278590		maoyiq	Mecho (IOI09_mecho)	C++20	87 / 100	100 ms	6812 KiB

mecho

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

int N, S;

const int MAXN=801;
char frst[MAXN][MAXN];
int hive[MAXN][MAXN], dest[MAXN][MAXN];

int dir[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

inline bool valid_loc(int x, int y) {
  return x >= 0 && x < N && y >= 0 && y < N;
}

int main() {
  cin >> N >> S;
  pair<int, int> mloc, dloc;
  memset(hive, -1, sizeof(hive));
  queue<pair<int, int>> bees;
  for (int i = 0; i < N; ++i) {
    cin >> frst[i];
    for (int j = 0; j < N; ++j) {
      if (frst[i][j] == 'H') {
        hive[i][j] = 0;
        bees.push({i, j});
      } else if (frst[i][j] == 'M') {
        mloc = {i, j};
      } else if (frst[i][j] == 'D') {
        dloc = {i, j};
      }
    }
  }

  while (!bees.empty()) {
    auto bee = bees.front();
    bees.pop();

    for (int k = 0; k < 4; ++k) {
      int x = bee.first + dir[k][0], y = bee.second + dir[k][1];
      if (valid_loc(x, y) && hive[x][y] == -1 && (frst[x][y] == 'G' || frst[x][y] == 'M')) {
        hive[x][y] = hive[bee.first][bee.second] + 1;
        bees.push({x, y});
      }
    }
  }

  memset(dest, -1, sizeof(dest));
  priority_queue<pair<pair<int, int>, pair<int, int>>> bears;
  dest[dloc.first][dloc.second] = 1000000;
  bears.push({{1000000, 1}, {dloc.first, dloc.second}});
  while (!bears.empty()) {
    auto bear = bears.top().second;
    auto step = bears.top().first.second;
    bears.pop();
    // cerr << bear.first << "," << bear.second << " " << dest[bear.first][bear.second] << ":" << step << endl;

    for (int k = 0; k < 4; ++k) {
      int x = bear.first + dir[k][0], y = bear.second + dir[k][1];
      if (valid_loc(x, y) && dest[x][y] == -1 && (frst[x][y] == 'G' || frst[x][y] == 'M')) {
        int ss = step;
        int dd = dest[bear.first][bear.second];
        if (ss == 1) {
          ss = S;
          dd -= 1;
        } else {
          ss -= 1;
        }
        if (dd < 0) {
          continue;
        }

        if (hive[x][y] > 1 && hive[x][y] <= dd) {
          dd = hive[x][y] - 1;
        }

        dest[x][y] = dd;
        bears.push({{dd, ss}, {x, y}});
      }
    }
  }

  cout << dest[mloc.first][mloc.second] << endl;

  return 0;
}

• Subtask 1: 87 / 100