Submission #1155245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155245		i_liek_cheezits	Mecho (IOI09_mecho)	C++20	29 / 100	229 ms	7120 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
template<typename T> bool ckmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0; 
}
const int INF = (int)1e9; 
const int MAXN = 805; 
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; 
string grid[MAXN]; 
bool visited[MAXN][MAXN]; 
int dist[MAXN][MAXN], prev_dist[MAXN][MAXN]; 
pii start; 
vector<pii> hives; 
struct Entry {
    pii p; int dist; int timer; 
}; 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int n, s; cin >> n >> s;
  for(int i = 0; i < n; i++) {
      cin >> grid[i]; 
      for(int j = 0; j < n; j++) {
          prev_dist[i][j] = INF; 
          if (grid[i][j] == 'M') {
              prev_dist[i][j] = 0;
              start = {i, j}; 
          } 
          if (grid[i][j] == 'H') {
              prev_dist[i][j] = 0;
              hives.push_back({i, j}); 
          }
      }
  }
  int l = 0, r = 3000;
  queue<pii> q; 
  while(l < r) {
      int m = (l+r+1)/2; 
      for(int i = 0; i < n; i++) {
          for(int j = 0; j < n; j++) dist[i][j] = prev_dist[i][j]; 
      }
      memset(visited, false, sizeof(visited)); 
      for(pii &x : hives) q.push(x); 
      while(sz(q)) {
          pii p = q.front(); q.pop(); 
          for(int i = 0; i < 4; i++) {
              pii np = {p.f + dx[i], p.s + dy[i]};
              if (np.f >= 0 && np.s >= 0 && np.f < n && np.s < n
              && grid[np.f][np.s] != 'T' && grid[np.f][np.s] != 'D'
              && ckmin(dist[np.f][np.s], dist[p.f][p.s]+1)) {
                  q.push(np); 
              } 
          }
      }
      bool ok = false; 
      queue<Entry> q2; 
      q2.push({start, 0, 0});
      while(sz(q2)) {
          auto [p, d, t] = q2.front(); q2.pop(); 
          //if (m == 1) cout << p.f << " " << p.s << " " << d << " " << t << '\n';
          visited[p.f][p.s] = true;
          if (grid[p.f][p.s] == 'D') {
              ok = true; break; 
          }
          for(int i = 0; i < 4; i++) {
              pii np = {p.f + dx[i], p.s + dy[i]};
              if (np.f >= 0 && np.s >= 0 && np.f < n && np.s < n
              && grid[np.f][np.s] != 'T') {
                  
                  if (ckmin(dist[np.f][np.s], d + m + (t == 0))
                  || (!visited[np.f][np.s] && dist[np.f][np.s] == d + m + (t==0))) {
                 dist[np.f][np.s] =  d + m + (t == 0); 
                 visited[np.f][np.s] = true;
                 if (t) {
                     q2.push({np, d, t-1}); 
                 } else {
                     q2.push({np, d+1, s-1}); 
                 }
                  }
              } 
          }
      }
      if (ok) l = m; 
      else r = m-1; 
  }
  cout << l << "\n"; 
  
  return 0;
}

• Subtask 1: 29 / 100