oj.uz

Submission #541302

# Submission time Handle Problem Language Result Execution time Memory
541302 2022-03-23T01:16:49 Z SquareSpoon Mecho (IOI09_mecho) C++14
20 / 100
 137 ms 5936 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 900 KB Output isn't correct
2 Incorrect 1 ms 852 KB Output isn't correct
3 Incorrect 1 ms 852 KB Output isn't correct
4 Incorrect 1 ms 852 KB Output isn't correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 112 ms 5532 KB Output is correct
8 Incorrect 1 ms 980 KB Output isn't correct
9 Incorrect 1 ms 980 KB Output isn't correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 944 KB Output is correct
12 Incorrect 1 ms 1204 KB Output isn't correct
13 Incorrect 1 ms 1108 KB Output isn't correct
14 Incorrect 1 ms 1236 KB Output isn't correct
15 Incorrect 1 ms 980 KB Output isn't correct
16 Incorrect 1 ms 980 KB Output isn't correct
17 Incorrect 1 ms 980 KB Output isn't correct
18 Incorrect 1 ms 952 KB Output isn't correct
19 Incorrect 1 ms 980 KB Output isn't correct
20 Incorrect 1 ms 980 KB Output isn't correct
21 Incorrect 1 ms 1108 KB Output isn't correct
22 Incorrect 1 ms 1108 KB Output isn't correct
23 Incorrect 1 ms 1072 KB Output isn't correct
24 Incorrect 1 ms 1108 KB Output isn't correct
25 Incorrect 1 ms 1108 KB Output isn't correct
26 Incorrect 1 ms 1108 KB Output isn't correct
27 Incorrect 1 ms 1236 KB Output isn't correct
28 Incorrect 1 ms 1236 KB Output isn't correct
29 Incorrect 1 ms 1236 KB Output isn't correct
30 Incorrect 1 ms 1236 KB Output isn't correct
31 Incorrect 1 ms 1236 KB Output isn't correct
32 Incorrect 2 ms 1236 KB Output isn't correct
33 Incorrect 11 ms 2624 KB Output isn't correct
34 Incorrect 12 ms 2624 KB Output isn't correct
35 Correct 19 ms 2704 KB Output is correct
36 Incorrect 14 ms 2868 KB Output isn't correct
37 Incorrect 15 ms 2880 KB Output isn't correct
38 Correct 23 ms 2864 KB Output is correct
39 Incorrect 17 ms 3156 KB Output isn't correct
40 Incorrect 19 ms 3204 KB Output isn't correct
41 Correct 29 ms 3268 KB Output is correct
42 Incorrect 20 ms 3484 KB Output isn't correct
43 Incorrect 22 ms 3404 KB Output isn't correct
44 Correct 35 ms 3504 KB Output is correct
45 Incorrect 25 ms 3788 KB Output isn't correct
46 Incorrect 27 ms 3764 KB Output isn't correct
47 Correct 43 ms 3764 KB Output is correct
48 Incorrect 29 ms 4072 KB Output isn't correct
49 Incorrect 31 ms 4044 KB Output isn't correct
50 Correct 58 ms 4144 KB Output is correct
51 Incorrect 35 ms 4288 KB Output isn't correct
52 Incorrect 38 ms 4404 KB Output isn't correct
53 Correct 59 ms 4396 KB Output is correct
54 Incorrect 38 ms 4648 KB Output isn't correct
55 Incorrect 42 ms 4652 KB Output isn't correct
56 Correct 69 ms 4712 KB Output is correct
57 Incorrect 45 ms 4896 KB Output isn't correct
58 Incorrect 49 ms 4904 KB Output isn't correct
59 Correct 77 ms 4916 KB Output is correct
60 Incorrect 49 ms 5296 KB Output isn't correct
61 Incorrect 52 ms 5284 KB Output isn't correct
62 Correct 88 ms 5232 KB Output is correct
63 Incorrect 55 ms 5328 KB Output isn't correct
64 Incorrect 137 ms 5364 KB Output isn't correct
65 Incorrect 124 ms 5316 KB Output isn't correct
66 Incorrect 51 ms 5216 KB Output isn't correct
67 Incorrect 69 ms 5208 KB Output isn't correct
68 Incorrect 57 ms 5612 KB Output isn't correct
69 Incorrect 66 ms 5604 KB Output isn't correct
70 Incorrect 54 ms 5532 KB Output isn't correct
71 Incorrect 57 ms 5580 KB Output isn't correct
72 Incorrect 55 ms 5568 KB Output isn't correct
73 Incorrect 63 ms 5796 KB Output isn't correct
74 Correct 96 ms 5924 KB Output is correct
75 Correct 98 ms 5936 KB Output is correct
76 Correct 104 ms 5892 KB Output is correct
77 Correct 95 ms 5908 KB Output is correct
78 Incorrect 103 ms 5728 KB Output isn't correct
79 Correct 96 ms 5676 KB Output is correct
80 Correct 102 ms 5760 KB Output is correct
81 Correct 107 ms 5840 KB Output is correct
82 Correct 99 ms 5836 KB Output is correct
83 Correct 115 ms 5704 KB Output is correct
84 Correct 114 ms 5676 KB Output is correct
85 Correct 111 ms 5700 KB Output is correct
86 Correct 106 ms 5772 KB Output is correct
87 Correct 103 ms 5652 KB Output is correct
88 Correct 114 ms 5576 KB Output is correct
89 Correct 108 ms 5640 KB Output is correct
90 Correct 110 ms 5584 KB Output is correct
91 Correct 108 ms 5644 KB Output is correct
92 Correct 108 ms 5580 KB Output is correct