Submission #541208

#	Time	Username	Problem	Language	Result	Execution time	Memory
541208		SquareSpoon	Mecho (IOI09_mecho)	C++14	4 / 100	67 ms	6016 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], v2[MAX][MAX];
int x[5] = {1, 0, -1, 0};
int y[5] = {0, 1, 0, -1};
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] = 1;
  }
  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] + 1;

      q.push(make_pair(x1, y1));
    }
  }
}
int bfs(int c1, int c2, int steps, int time){
  queue<pair<int, pair<int, pii> > > q;
  q.push(make_pair(time, make_pair(steps, make_pair(c1, c2))));
  int res = 0;
  while(!q.empty()){
     pii node = q.front().second.second;
     int stps = q.front().second.first;
     int dist = 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] << '\n';
       if(v2[x1][y1] || map[x1][y1] == 'T' || d[x1][y1] <= dist || map[x1][y1] == 'H' || map[x1][y1] == 'D') continue;
       if(stps == 0){
          stps = steps;
          dist--;
       }
       //cout << stps << " " << dist << '\n';
       if(map[x1][y1] == 'M'){
          //if(stps == 1) dist--;
          return dist;
       }
       q.push(make_pair(dist, make_pair(stps-1, make_pair(x1, y1))));
     }
  }
  return -1;
}
int main(){
    cin >> n >> m;
    vector<pii> cords;
    int xs, ys;
    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;
        }
      }
    }
    bees(cords);
    int time = 0, idx;
    for(int i = 0; i < 4; i++){
      int x1 = xs + x[i];
      int y1 = ys + y[i];
      if(x1 < 1 || x1 > n || y1 < 1 || y1 > n) continue;
      if(map[x1][y1] != 'G') continue;
      if(d[x1][y1] > time){
        time = d[x1][y1];
        idx = i;
      }
    }
    time--;
    int path = bfs(xs, ys, m, time);
    if(path == -1 || time - path < 0) cout << -1 << '\n';
    else cout << time - path << '\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:16: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]
   16 |   for(int i = 0; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
mecho.cpp: In function 'int bfs(int, int, int, int)':
mecho.cpp:39:7: warning: unused variable 'res' [-Wunused-variable]
   39 |   int res = 0;
      |       ^~~
mecho.cpp: In function 'int main()':
mecho.cpp:82:19: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
   82 |     int time = 0, idx;
      |                   ^~~
mecho.cpp:85:11: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |       int y1 = ys + y[i];
      |           ^~
mecho.cpp:84:11: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |       int x1 = xs + x[i];
      |           ^~

• Subtask 1: 4 / 100