Submission #1180015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180015		julia_08	Mecho (IOI09_mecho)	C++20	100 / 100	143 ms	11484 KiB

mecho

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

const int MAXN = 810;

int dist[MAXN][MAXN], marc[MAXN][MAXN];

int dist_bee[MAXN][MAXN], marc_bee[MAXN][MAXN];

char a[MAXN][MAXN];

int n, s;

pair<int, int> st, en;
vector<pair<int, int>> bees;

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

bool in(int i, int j){
  return 0 < i && i <= n && 0 < j && j <= n;
}

void bfs_bees(){

  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      dist_bee[i][j] = 1e9;
    }
  }

  queue<pair<int, int>> q;

  for(auto [i, j] : bees) q.push({i, j}), dist_bee[i][j] = 0, marc_bee[i][j] = 1;

  while(!q.empty()){

    auto [i, j] = q.front(); q.pop();

    for(int k=0; k<4; k++){

      int ni = i + dx[k], nj = j + dy[k];

      if(!in(ni, nj) || marc_bee[ni][nj] || a[ni][nj] == 'T' || a[ni][nj] == 'D') continue;

      marc_bee[ni][nj] = 1;
      dist_bee[ni][nj] = dist_bee[i][j] + 1;

      q.push({ni, nj});

    }

  }

}

bool check(int t){

  if(t < 0) return true;

  if(dist_bee[st.first][st.second] <= t) return false;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      dist[i][j] = 1e9;
      marc[i][j] = 0;
    }
  }

  queue<pair<int, int>> q;

  q.push(st); dist[st.first][st.second] = 0; marc[st.first][st.second] = 1;

  while(!q.empty()){

    auto [i, j] = q.front(); q.pop();

    for(int k=0; k<4; k++){

      int ni = i + dx[k], nj = j + dy[k];

      if(!in(ni, nj) || marc[ni][nj] || a[ni][nj] == 'T') continue;

      if(dist_bee[ni][nj] <= t + (dist[i][j] + 1) / s) continue;

      marc[ni][nj] = 1;
      dist[ni][nj] = dist[i][j] + 1;

      q.push({ni, nj});

    }

  }

  return marc[en.first][en.second];
}

int bs(){

  int l = -1, r = n * n;

  while(l < r){
    int m = l + (r - l + 1) / 2;
    if(check(m)) l = m;
    else r = m - 1;
  }

  return l;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> s;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){

      cin >> a[i][j];

      if(a[i][j] == 'M') st = {i, j};
      if(a[i][j] == 'D') en = {i, j};
      if(a[i][j] == 'H') bees.push_back({i, j});

    }
  }

  bfs_bees();

  cout << bs() << "\n";

  return 0;
}

• Subtask 1: 100 / 100