oj.uz

Submission #501944

# Submission time Handle Problem Language Result Execution time Memory
501944 2022-01-04T21:50:54 Z lorenzoferrari Mecho (IOI09_mecho) C++17
0 / 100
 37 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int32_t main() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  int n, s;
  cin >> n >> s;
  vector<vector<char>> m(n, vector<char> (n));
  int xs, ys;
  int xe, ye;
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    cin >> m[i][j];
    if (m[i][j] == 'M') xs = i, ys = j;
    if (m[i][j] == 'D') xe = i, ye = j;
  }
  queue<pair<int, int>> Q;
  vector<vector<int>> d(n, vector<int> (n, 1e9));
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    if (m[i][j] == 'H') {
      d[i][j] = 0;
      Q.push({i, j});
    }
  }
  while (!Q.empty()) {
    auto [x, y] = Q.front();
    Q.pop();
    if (x     && (m[x-1][y  ] == 'G' || m[x-1][y  ] == 'M') && d[x-1][y  ] > d[x][y] + 1) d[x-1][y  ] = d[x][y] + 1, Q.push({x-1, y  });
    if (y     && (m[x  ][y-1] == 'G' || m[x  ][y-1] == 'M') && d[x  ][y-1] > d[x][y] + 1) d[x  ][y-1] = d[x][y] + 1, Q.push({x  , y-1});
    if (x<n-1 && (m[x+1][y  ] == 'G' || m[x+1][y  ] == 'M') && d[x+1][y  ] > d[x][y] + 1) d[x+1][y  ] = d[x][y] + 1, Q.push({x+1, y  });
    if (y<n-1 && (m[x  ][y+1] == 'G' || m[x  ][y+1] == 'M') && d[x  ][y+1] > d[x][y] + 1) d[x  ][y+1] = d[x][y] + 1, Q.push({x  , y+1});
  }
  auto psb = [&](int delay) {
    // bfs from mecho's location
    // it's possible iff dist_from_mecho[i][j]/s + delay < d[i][j]
    queue<pair<int, int>> Q;
    vector<vector<int>> dm(n, vector<int> (n, 1e9));
    Q.push({xs, ys});
    dm[xs][ys] = 0;
    while (!Q.empty()) {
      auto [x, y] = Q.front();
      Q.pop();
      if (delay + (dm[x][y]) / s >= d[x][y]) continue;
      if (x     && m[x-1][y  ] != 'T' && dm[x-1][y  ] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x-1][y  ]) dm[x-1][y  ] = dm[x][y] + 1, Q.push({x-1, y  });
      if (y     && m[x  ][y-1] != 'T' && dm[x  ][y-1] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x  ][y-1]) dm[x  ][y-1] = dm[x][y] + 1, Q.push({x  , y-1});
      if (x<n-1 && m[x+1][y  ] != 'T' && dm[x+1][y  ] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x+1][y  ]) dm[x+1][y  ] = dm[x][y] + 1, Q.push({x+1, y  });
      if (y<n-1 && m[x  ][y+1] != 'T' && dm[x  ][y+1] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x  ][y+1]) dm[x  ][y+1] = dm[x][y] + 1, Q.push({x  , y+1});
    }
    return dm[xe][ye] != 1e9;
  };
  int l = 0, r = n * n + 2;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (psb(mid))
      l = mid;
    else
      r = mid;
  }
  cout << (psb(l) ? l : -1) << "\n";
}

Compilation message

mecho.cpp: In function 'int32_t main()':
mecho.cpp:6:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:7:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Runtime error 2 ms 460 KB Execution killed with signal 6
3 Runtime error 2 ms 484 KB Execution killed with signal 6
4 Runtime error 2 ms 460 KB Execution killed with signal 6
5 Runtime error 29 ms 65540 KB Execution killed with signal 9
6 Runtime error 28 ms 65540 KB Execution killed with signal 9
7 Runtime error 4 ms 460 KB Execution killed with signal 6
8 Runtime error 27 ms 65540 KB Execution killed with signal 9
9 Runtime error 2 ms 460 KB Execution killed with signal 6
10 Runtime error 35 ms 65540 KB Execution killed with signal 9
11 Runtime error 2 ms 484 KB Execution killed with signal 6
12 Runtime error 29 ms 65540 KB Execution killed with signal 9
13 Runtime error 27 ms 65540 KB Execution killed with signal 9
14 Runtime error 29 ms 65540 KB Execution killed with signal 9
15 Runtime error 25 ms 65540 KB Execution killed with signal 9
16 Runtime error 32 ms 65540 KB Execution killed with signal 9
17 Runtime error 30 ms 65540 KB Execution killed with signal 9
18 Runtime error 28 ms 65540 KB Execution killed with signal 9
19 Runtime error 2 ms 460 KB Execution killed with signal 6
20 Runtime error 29 ms 65540 KB Execution killed with signal 9
21 Runtime error 2 ms 460 KB Execution killed with signal 6
22 Runtime error 29 ms 65540 KB Execution killed with signal 9
23 Runtime error 2 ms 460 KB Execution killed with signal 6
24 Runtime error 26 ms 65540 KB Execution killed with signal 9
25 Runtime error 26 ms 65540 KB Execution killed with signal 9
26 Runtime error 2 ms 460 KB Execution killed with signal 6
27 Runtime error 2 ms 460 KB Execution killed with signal 6
28 Runtime error 3 ms 460 KB Execution killed with signal 6
29 Runtime error 2 ms 460 KB Execution killed with signal 6
30 Runtime error 37 ms 65540 KB Execution killed with signal 9
31 Runtime error 2 ms 460 KB Execution killed with signal 6
32 Runtime error 2 ms 460 KB Execution killed with signal 6
33 Runtime error 26 ms 65540 KB Execution killed with signal 9
34 Runtime error 25 ms 65540 KB Execution killed with signal 9
35 Runtime error 27 ms 65540 KB Execution killed with signal 9
36 Runtime error 2 ms 460 KB Execution killed with signal 6
37 Runtime error 2 ms 512 KB Execution killed with signal 6
38 Runtime error 2 ms 460 KB Execution killed with signal 6
39 Runtime error 2 ms 460 KB Execution killed with signal 6
40 Runtime error 34 ms 65540 KB Execution killed with signal 9
41 Runtime error 2 ms 460 KB Execution killed with signal 6
42 Runtime error 25 ms 65540 KB Execution killed with signal 9
43 Runtime error 26 ms 65540 KB Execution killed with signal 9
44 Runtime error 2 ms 460 KB Execution killed with signal 6
45 Runtime error 2 ms 460 KB Execution killed with signal 6
46 Runtime error 2 ms 460 KB Execution killed with signal 6
47 Runtime error 26 ms 65540 KB Execution killed with signal 9
48 Runtime error 27 ms 65540 KB Execution killed with signal 9
49 Runtime error 2 ms 460 KB Execution killed with signal 6
50 Runtime error 2 ms 460 KB Execution killed with signal 6
51 Runtime error 26 ms 65540 KB Execution killed with signal 9
52 Runtime error 3 ms 460 KB Execution killed with signal 6
53 Runtime error 2 ms 460 KB Execution killed with signal 6
54 Runtime error 33 ms 65540 KB Execution killed with signal 9
55 Runtime error 2 ms 460 KB Execution killed with signal 6
56 Runtime error 28 ms 65540 KB Execution killed with signal 9
57 Runtime error 28 ms 65540 KB Execution killed with signal 9
58 Runtime error 2 ms 460 KB Execution killed with signal 6
59 Runtime error 2 ms 460 KB Execution killed with signal 6
60 Runtime error 26 ms 65540 KB Execution killed with signal 9
61 Runtime error 3 ms 480 KB Execution killed with signal 6
62 Runtime error 31 ms 65540 KB Execution killed with signal 9
63 Runtime error 30 ms 65540 KB Execution killed with signal 9
64 Runtime error 2 ms 460 KB Execution killed with signal 6
65 Runtime error 3 ms 460 KB Execution killed with signal 6
66 Runtime error 2 ms 460 KB Execution killed with signal 6
67 Runtime error 2 ms 460 KB Execution killed with signal 6
68 Runtime error 2 ms 460 KB Execution killed with signal 6
69 Runtime error 2 ms 460 KB Execution killed with signal 6
70 Runtime error 27 ms 65540 KB Execution killed with signal 9
71 Runtime error 26 ms 65540 KB Execution killed with signal 9
72 Runtime error 3 ms 460 KB Execution killed with signal 6
73 Runtime error 3 ms 460 KB Execution killed with signal 6
74 Runtime error 28 ms 65540 KB Execution killed with signal 9
75 Runtime error 2 ms 460 KB Execution killed with signal 6
76 Runtime error 3 ms 460 KB Execution killed with signal 6
77 Runtime error 2 ms 460 KB Execution killed with signal 6
78 Runtime error 29 ms 65540 KB Execution killed with signal 9
79 Runtime error 27 ms 65540 KB Execution killed with signal 9
80 Runtime error 28 ms 65540 KB Execution killed with signal 9
81 Runtime error 30 ms 65540 KB Execution killed with signal 9
82 Runtime error 27 ms 65540 KB Execution killed with signal 9
83 Runtime error 2 ms 460 KB Execution killed with signal 6
84 Runtime error 2 ms 460 KB Execution killed with signal 6
85 Runtime error 2 ms 460 KB Execution killed with signal 6
86 Runtime error 3 ms 460 KB Execution killed with signal 6
87 Runtime error 3 ms 460 KB Execution killed with signal 6
88 Runtime error 3 ms 460 KB Execution killed with signal 6
89 Runtime error 26 ms 65540 KB Execution killed with signal 9
90 Runtime error 2 ms 484 KB Execution killed with signal 6
91 Runtime error 2 ms 460 KB Execution killed with signal 6
92 Runtime error 2 ms 460 KB Execution killed with signal 6