Submission #541302

#	Time	Username	Problem	Language	Result	Execution time	Memory
541302		SquareSpoon	Mecho (IOI09_mecho)	C++14	20 / 100	137 ms	5936 KiB

mecho

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
#define MAX 801
using namespace std;
typedef pair<int, int> pii;
int n, m, d[MAX][MAX];
char map[MAX][MAX];
bool v[MAX][MAX];
int x[5] = {1, 0, -1, 0};
int y[5] = {0, 1, 0, -1};
//calcular o tempo em passos
void bees(vector<pii> c){
  queue<pii> q;
  for(int i = 0; i < c.size(); i++){
     q.push(c[i]);
     d[c[i].first][c[i].second] = m;
  }
  while(!q.empty()){
    pii node = q.front();
    q.pop();
    if(v[node.first][node.second]) continue;
    v[node.first][node.second] = true;
    for(int i = 0; i < 4; i++){
      int x1 = x[i] + node.first;
      int y1 = y[i] + node.second;
      if(x1 > n || x1 < 1 || y1 > n || y1 < 1) continue;
      if(v[x1][y1]) continue;
      if(d[x1][y1] > d[node.first][node.second] + 1 || d[x1][y1] == 0) d[x1][y1] = d[node.first][node.second] + m;

      q.push(make_pair(x1, y1));
    }
  }
}
int bfs(int c1, int c2, int steps, int time){
  queue<pair<int, pii > > q;
  bool v2[MAX][MAX];
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++) v2[i][j] = false;
  q.push(make_pair(time, make_pair(c1, c2)));
  while(!q.empty()){
     pii node = q.front().second;
     int stps = q.front().first;
     q.pop();
     if(v2[node.first][node.second]) continue;
     v2[node.first][node.second] = true;
     for(int i = 0; i < 4; i++){
       int x1 = x[i] + node.first;
       int y1 = y[i] + node.second;
       if(x1 < 1 || x1 > n || y1 < 1 || y1 > n) continue;
       //cout << x1 << " " << y1 << " " << d[x1][y1] << " " << map[x1][y1] << " " << v2[x1][y1] << '\n';
       if(v2[x1][y1] || map[x1][y1] == 'T' || d[x1][y1] <= stps || map[x1][y1] == 'H' || map[x1][y1] == 'M') continue;
       //cout << stps << '\n';
       //cout << x1 << " " << y1 << " " << d[x1][y1] << '\n';
       if(map[x1][y1] == 'D'){
          //cout << "found" << '\n';
          int res = stps/m;

          return res;
       }
       q.push(make_pair(stps+1, make_pair(x1, y1)));
     }
  }
  return -1;
}
int main(){
    cin >> n >> m;
    vector<pii> cords;
    int xs, ys, xs1, ys1;
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        cin >> map[i][j];
        if(map[i][j] == 'H'){
          cords.push_back(make_pair(i, j));
        } else if(map[i][j] == 'D'){
          xs = i, ys = j;
        } else if(map[i][j] == 'M'){
          xs1 = i, ys1 = j;
        }
      }
    }
    bees(cords);
    int limit = 0;
    for(int i = 0; i < 4; i++){
      int x1 = xs + x[i];
      int y1 = ys + y[i];
      if(x1 > n || x1 < 1 || y1 < 1 || y1 > n) continue;
      limit = max(limit, d[x1][y1]);
    }
    int l = 1, r = (limit - m)/m;
    int mid = (l+r)/2;
    int res = -1;
    int path;
    d[xs][ys] = MAX*m;
    while(l <= r){
      path = bfs(xs1, ys1, m, mid*m);
      //cout << path << '\n';
      if(path == -1){
        r = mid - 1;
      } else{
        l = mid + 1;
        res = max(res, mid);
      }
      //cout << mid << " ";
      mid = (l+r)/2;
      path = 0;
    }
    cout << res-1 << '\n';
    //cout << path << " " << time << '\n';
    /*for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        cout << d[i][j] << " ";
      }
      cout << '\n';
    }*/
  }

Compilation message (stderr)

mecho.cpp: In function 'void bees(std::vector<std::pair<int, int> >)':
mecho.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int i = 0; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:98:17: warning: 'ys1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |       path = bfs(xs1, ys1, m, mid*m);
      |              ~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:88:11: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |       int y1 = ys + y[i];
      |           ^~
mecho.cpp:98:17: warning: 'xs1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |       path = bfs(xs1, ys1, m, mid*m);
      |              ~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:11: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |       int x1 = xs + x[i];
      |           ^~

• Subtask 1: 20 / 100