Submission #1200475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200475		SonicML	Mecho (IOI09_mecho)	C++20	26 / 100	731 ms	131072 KiB

mecho

#include <iostream>
#include <queue>

using namespace std;

typedef short sh;

int const INF = 1e9+7;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

int const NMAX = 800;
char mat[1 + NMAX][1 + NMAX];
int bee[1 + NMAX][1 + NMAX];

bool isValid(pair <sh, sh> to, int n) {
  return (1 <= to.first && to.first <= n && 1 <= to.second && to.second <= n &&
	  (mat[to.first][to.second] == 'G' || mat[to.first][to.second] == 'M' || mat[to.first][to.second] == 'D'));
}

void beeBFS(int n, int step) {
  queue <pair <sh, sh>> q;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      bee[i][j] = INF;
      if(mat[i][j] == 'H') {
	bee[i][j] = 0; 
	q.push({i, j});
      } 
    }
  }
  while(!q.empty()) {
    pair <sh, sh> from = q.front();
    q.pop();
    for(int dir = 0;dir < 4;dir++) {
      pair <sh, sh> to = {from.first + dirX[dir], from.second + dirY[dir]};
      if(isValid(to, n)) {
	if(bee[from.first][from.second] + step < bee[to.first][to.second]) {
	  bee[to.first][to.second] = bee[from.first][from.second] + step;
          q.push(to); 
	}
      }
    }
  }
}

int bear[1 + NMAX][1 + NMAX];

bool bearBFS(int n, int start) {
  queue <pair <sh, sh>> q;
  pair <sh, sh> fin;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      bear[i][j] = INF;
      if(mat[i][j] == 'M') {
	bear[i][j] = start;
	q.push({i, j});
      }
      if(mat[i][j] == 'D') {
	fin = {i, j};
      }
    }
  } 
  while(!q.empty()) {
    pair <sh, sh> from = q.front();
    q.pop();
    if(bear[from.first][from.second] < bee[from.first][from.second]) {
      for(int dir = 0;dir < 4;dir++) {
	pair <sh, sh> to = {from.first + dirX[dir], from.second + dirY[dir]};
	if(isValid(to, n) && bear[from.first][from.second] + 1 <= bear[to.first][to.second]) {
          bear[to.first][to.second] = bear[from.first][from.second] + 1;
          q.push(to);
        }
      }
    }
  } 
  if(bear[fin.first][fin.second] <= bee[fin.first][fin.second]) {
    return true;
  }
  return false;
}

int cautbin(int from, int to, int n) {
  if(from >= to) {
    return from;
  } else {
    int mid = (from + to + 1) / 2;
    if(bearBFS(n, mid)) {
      return cautbin(mid, to, n);
    } else {
      return cautbin(from, mid-1, n);
    }
  }
}

void printBee(int n) {
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      cerr << bee[i][j] << ' ';
    }
    cerr << '\n';
  }
  cerr << '\n';
}
int main() {

  int n, step;
  cin >> n >> step;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      cin >> mat[i][j]; 
    }
  }
  beeBFS(n, step);
  cout << cautbin(0, n*n*step, n) / step;
  return 0;
}

• Subtask 1: 26 / 100