Submission #713718

#	Time	Username	Problem	Language	Result	Execution time	Memory
713718		vjudge1	Mecho (IOI09_mecho)	C++17	100 / 100	410 ms	2684 KiB

mecho

#include "bits/stdc++.h"
using namespace std;

#define ii pair<int,int>
#define iii tuple<int,int,int>

const int ms = 8e2 + 5;

char grid[ms][ms];
bool bees[ms][ms], mecho[ms][ms];
int n, s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
ii start, fim;
vector<ii> hives;

void step(queue<ii> &q){
  queue<ii> nq;
  while(!q.empty()){
    int x, y;
    tie(x, y) = q.front();
    q.pop();
    if(bees[x][y]) continue;

    for(int i=0; i<4; i++){
        int a = x +dx[i], b = y + dy[i];
        if(a < 0 || a>= n || b < 0 || b>=n || bees[a][b] || grid[a][b] == 'T' ) continue;
        
        if(!mecho[a][b]){
          mecho[a][b] = true;
          nq.push({a, b});
        }
    }
  }
  nq.swap(q);
}

void step_bees(queue<ii> &h){
  queue<ii> new_h;

  while(!h.empty()){
    int x, y;
    tie(x, y) = h.front();
    h.pop();

    for(int i=0; i<4; i++){
      int a = x+dx[i], b = y+dy[i];

      if(a < 0 || a >= n || b <0 || b >=n || grid[a][b] == 'T' || grid[a][b] == 'D') continue;

      if(!bees[a][b]){
        bees[a][b] = true;
        new_h.push({a, b});
      }
    }

  }
  new_h.swap(h);
}


bool test(int mid){
  memset(bees, 0, sizeof bees);
  memset(mecho, 0, sizeof mecho);

  queue<ii> h, m;

  mecho[start.first][start.second] = true;
  m.push(start);

  for(int i=0; i<hives.size(); i++) {
    bees[hives[i].first][hives[i].second] = true;
    h.push(hives[i]);
  }
  
  for(int i=0; i<mid; i++) step_bees(h);

  while(!m.empty()){

    for(int i=0; i<s; i++)step(m);
    
    step_bees(h);
  }

  return mecho[fim.first][fim.second];
}

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

  
  cin >> n >> s;
  

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin >> grid[i][j];
      if(grid[i][j] == 'M') start ={i, j};
      if(grid[i][j] == 'D') fim = {i, j};
      if(grid[i][j] == 'H') hives.push_back({i, j});
    }
  }


  int l=0, r = n*n;
  int ans = -1;
  while(l <= r){
    int mid = (l+r)/2;
    
    if(test(mid)){
      ans = mid;
      l = mid+1;
    }
    else r = mid -1;

  }
  // test(2);

  cout << ans << '\n';


	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool test(int)':
mecho.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0; i<hives.size(); i++) {
      |                ~^~~~~~~~~~~~~

• Subtask 1: 100 / 100