Submission #1135403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135403		mine255	Mecho (IOI09_mecho)	C++20	100 / 100	138 ms	3804 KiB

mecho

#include <bits/stdc++.h>
#define _FILE "TEMP"
#define ll long long
using namespace std;

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

int n,s,xm,ym;
char a[807][807];
int d[807][807];

bool check(int t) {
  if (t >= d[xm][ym]) return 0;

  queue<pair<pair<int,int>,ll>> q;
  vector<vector<bool>> f(n+7,vector<bool>(n+7,0));

  q.push({{xm,ym},1ll*s*t});
  f[xm][ym] = 1;

  while (!q.empty()) {
    int x = q.front().first.first;
    int y = q.front().first.second;
    ll cur = q.front().second;
    q.pop();

    // cerr << x << ' ' << y << ' ' << cur << '\n';

    if (a[x][y] == 'D') return 1;

    for (int i=0; i<4; i++) {
      int u = x + dx[i];
      int v = y + dy[i];

      if (u >= 1 && u <= n && v >= 1 && v <= n && (a[u][v] == 'G' || a[u][v] == 'D') && !f[u][v]) {
        if ((cur+1)%s != 0 && (cur+s)/s <= d[u][v]) {
          f[u][v] = 1;
          q.push({{u,v},cur+1});
        }
        else if ((cur+1)%s == 0 && (cur+1)/s < d[u][v]) {
          f[u][v] = 1;
          q.push({{u,v},cur+1});
        }
      }
    }
  }

  return 0;
}

int main() {

  ios_base::sync_with_stdio(0);
  cin.tie(nullptr); cout.tie(nullptr);

  #ifdef EMERGENCY_DEBUG
  freopen(_FILE".inp","r",stdin);
  freopen(_FILE".out","w",stdout);
  #endif

  cin >> n >> s;

  queue<pair<int,int>> q;
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++) {
      cin >> a[i][j];
      d[i][j] = 1e9;

      if (a[i][j] == 'H') {
        q.push({i,j});
        d[i][j] = 0;
      }

      if (a[i][j] == 'M') {
        xm = i;
        ym = j;
      }
    }
  }

  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    for (int i=0; i<4; i++) {
      int u = x + dx[i];
      int v = y + dy[i];

      if (u >= 1 && u <= n && v >= 1 && v <= n && a[u][v] != 'T' && a[u][v] != 'D' && d[u][v] == 1e9) {
        d[u][v] = d[x][y] + 1;
        q.push({u,v});
      }
    }
  }

  int l=-1, h=n*n;
  while (l < h) {
    int mid = l + (h-l+1)/2;

    if (check(mid)) l = mid;
    else h = mid - 1;
  }

  cout << l;

  return 0;
}

• Subtask 1: 100 / 100