Submission #386537

#	Time	Username	Problem	Language	Result	Execution time	Memory
386537		tushar_2658	Mecho (IOI09_mecho)	C++14	84 / 100	658 ms	8976 KiB

mecho

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

const int maxn = 805;

char s[maxn][maxn];
int n, S; 
int vis[maxn][maxn], dis[maxn][maxn], dis1[maxn][maxn];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int sx, sy, fx, fy;

void precalc(){
  using pii = pair<int, pair<int, int>>;
  priority_queue<pii, vector<pii>, greater<pii>> q;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j){
      dis[i][j] = n * n;
      if(s[i][j] == 'H'){
        q.push({0, {i, j}});
        dis[i][j] = 0;
      }
    }
  }
  while(!q.empty()){
    pii src = q.top();
    q.pop();   
    for(int i = 0; i < 4; ++i){
      int newx = src.second.first + dx[i], newy = src.second.second + dy[i];
      if(newx <= n && newx > 0 && newy <= n && newy > 0){
        if(dis[src.second.first][src.second.second] + 1 < dis[newx][newy] && s[newx][newy] != 'T' && s[newx][newy] != 'D'){
          dis[newx][newy] = dis[src.second.first][src.second.second] + 1;
          q.push({dis[newx][newy], {newx, newy}});
        }
      }
    }
  }
}

bool can(int x){
  using pii = pair<int, pair<int, int>>;
  priority_queue<pii, vector<pii>, greater<pii>> q;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j){
      dis1[i][j] = n * n;
      if(s[i][j] == 'T')vis[i][j] = 1;
      else if(s[i][j] == 'M'){
        vis[i][j] = 1;
        dis1[i][j] = 0;
        q.push({0, {i, j}});
      }else {
        vis[i][j] = 0;
      }
    }
  }
  while(!q.empty()){
    pii src = q.top();
    q.pop();
    for(int i = 0; i < 4; ++i){
      int newx = src.second.first + dx[i], newy = src.second.second + dy[i];
      if(newx <= n && newx > 0 && newy <= n && newy > 0){
        if(s[newx][newy] != 'T' && dis1[src.second.first][src.second.second] + 1 < dis1[newx][newy]){
          int cost = (dis1[src.second.first][src.second.second] + 1) / S + x; 
          if(cost < dis[newx][newy]){
            vis[newx][newy] = 1;
            dis1[newx][newy] = dis1[src.second.first][src.second.second] + 1;
            q.push({dis1[newx][newy], {newx, newy}});
          }
        }
      }
    }
  }
  if(vis[fx][fy])return 1;
  return 0;
}

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> S;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j){
      cin >> s[i][j];
      if(s[i][j] == 'M'){
        sx = i, sy = j;
      }else if(s[i][j] == 'D'){
        fx = i, fy = j;
      }
    }
  }
  precalc();
  int lo = 0, hi = n * n, ans = -1;
  while(lo <= hi){
    int mid = (lo + hi) >> 1;
    if(can(mid)){
      ans = mid;
      lo = mid + 1;
    }else {
      hi = mid - 1;
    }
  }
  cout << ans << '\n';

  return 0;
}

• Subtask 1: 84 / 100