Submission #1098029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098029		sexo69696969	Mecho (IOI09_mecho)	C++14	84 / 100	153 ms	6320 KiB

mecho

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

#ifdef local
  #include "debug.hpp"
  #define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
  #define prs(...) debug_nameless(__VA_ARGS__)
#else
  #define pr(...) 69
  #define prs(...) 69
#endif

#define endl '\n'

const int inf = 1e9;
const long long binf = 1e18;

void solve(int tc){
  int n, s;
  cin >> n >> s;
  int st = -1, ed = -1;
  vector <int> bees;
  auto get_hash = [&](int i, int j){
    return n*i + j;
  };
  vector <string> grid(n);
  for(int i = 0; i < n; i++){
    cin >> grid[i];
    for(int j = 0; j < n; j++){
      int hash = get_hash(i, j);
      if(grid[i][j] == 'M') st = hash;
      if(grid[i][j] == 'D') ed = hash;
      if(grid[i][j] == 'H') bees.push_back(hash);
    }
  }
  assert(bees.size() > 0 && st != -1 && ed != -1);
  vector <vector<int>> bdist(n, vector<int>(n, inf));
  queue <int> queue;
  for(int b : bees){
    queue.push(b);
    bdist[b/n][b%n] = 0;
  }
  auto inside = [&](int l, int c){
    return (min(l, c) >= 0 && max(l, c) < n && (grid[l][c] == 'G' || grid[l][c] == 'D' || grid[l][c] == 'M'));
  };
  while(queue.size() > 0){
    int node = queue.front();
    queue.pop();
    int l = node/n, c = node%n;
    for(int i = -1; i <= 1; i++){
      for(int j = -1; j <= 1; j++){
        if(i*j != 0) continue;
        if(inside(l+i, c+j) && grid[l+i][c+j] != 'D' && bdist[l+i][c+j] > s + bdist[l][c]){
          queue.push(get_hash(l+i, c+j));
          bdist[l+i][c+j] = s + bdist[l][c];
        }
      }
    }
  }
  auto check = [&](int t){
    while(queue.size()) queue.pop();
    vector <vector<int>> dist(n, vector<int>(n, inf));
    dist[st/n][st%n] = s*t;
    queue.push(st);
    while(queue.size() > 0){
      int node = queue.front();
      queue.pop();
      int l = node/n, c = node%n;
      for(int i = -1; i <= 1; i++){
        for(int j = -1; j <= 1; j++){
          if(i*j != 0) continue;
          if(inside(l+i, c+j) && bdist[l+i][c+j] > 1 + dist[l][c] && 1+dist[l][c] < dist[l+i][c+j]){
            queue.push(get_hash(l+i, c+j));
            dist[l+i][c+j] = 1 + dist[l][c];
          }
        }
      }
    }
    int l = ed/n, c = ed%n;
    for(int i = -1; i <= 1; i++){
      for(int j = -1; j <= 1; j++){
        if(i*j != 0) continue;
        if(inside(l+i, c+j) && dist[l+i][c+j] < bdist[l+i][c+j]){
          return true;
        }
      }
    }
    return false;
  };
  int l = 0, r = 1e6;
  int ans = -1;
  while(l <= r){
    int mid = (l + r)/2;
    if(check(mid)){
      l = mid+1;
      ans = mid;
    }else{
      r = mid-1;
    }
  }
  cout << ans << endl;
}  

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0);

  int tt = 1;
  while(tt--){
    prs(string(50, '-'));
    solve(tt);
    prs(string(50, '-'));
  }

  return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 |   #define prs(...) 69
      |                    ^~
mecho.cpp:109:5: note: in expansion of macro 'prs'
  109 |     prs(string(50, '-'));
      |     ^~~
mecho.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 |   #define prs(...) 69
      |                    ^~
mecho.cpp:111:5: note: in expansion of macro 'prs'
  111 |     prs(string(50, '-'));
      |     ^~~

• Subtask 1: 84 / 100