oj.uz

Submission #1079759

# Submission time Handle Problem Language Result Execution time Memory
1079759 2024-08-29T00:58:55 Z juicy Mecho (IOI09_mecho) C++17
25 / 100
 257 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);  

  int n, k; cin >> n >> k;
  vector a(n, vector<char>(n));
  vector d(n, vector<int>(n, -1));
  queue<array<int, 2>> q;
  array<int, 2> s{}, t{};
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
      if (a[i][j] == 'H') {
        q.push({i, j});
        d[i][j] = 0;
      } else if (a[i][j] == 'M') {
        s = {i, j};
      } else if (a[i][j] == 'D') {
        t = {i, j};
      }
    }
  }
  auto inside = [&](int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < n;
  };
  while (q.size()) {
    auto [i, j] = q.front(); q.pop();
    for (int dr = 0; dr < 4; ++dr) {
      int u = i + dx[dr], v = j + dy[dr];
      if (inside(u, v) && a[u][v] != 'T' && a[u][v] != 'H' && d[u][v] == -1) {
        d[u][v] = d[i][j] + 1;
        q.push({u, v});
      }
    }
  } 
  auto check = [&](int md) -> bool {
    vector c(n, vector<int>(n, -1));
    queue<array<int, 2>>().swap(q);
    q.push(s);
    c[s[0]][s[1]] = 0;
    while (q.size()) {
      auto [i, j] = q.front(); q.pop();
      if (tie(i, j) == tie(t[0], t[1])) {
        return 1;
      }
      if (md + c[i][j] / k >= d[i][j]) {
        continue;
      }
      for (int dr = 0; dr < 4; ++dr) {
        int u = i + dx[dr], v = j + dy[dr];
        if (inside(u, v) && a[u][v] != 'T' && a[u][v] != 'H' && c[u][v]) {
          c[u][v] = c[i][j] + 1;
          q.push({u, v});
        }
      }
    }
    return 0;
  };
  int l = 0, r = n * n, res = -1;
  while (l <= r) {
    int md = (l + r) / 2;
    if (check(md)) {
      res = md;
      l = md + 1;
    } else {
      r = md - 1;
    }
  } 
  cout << res;
  return 0;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 5 ms 828 KB Output is correct
7 Runtime error 144 ms 65536 KB Execution killed with signal 9
8 Correct 1 ms 348 KB Output is correct
9 Correct 145 ms 54668 KB Output is correct
10 Correct 23 ms 4956 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Runtime error 134 ms 65536 KB Execution killed with signal 9
14 Runtime error 152 ms 65536 KB Execution killed with signal 9
15 Correct 0 ms 348 KB Output is correct
16 Runtime error 257 ms 65536 KB Execution killed with signal 9
17 Correct 1 ms 348 KB Output is correct
18 Runtime error 185 ms 65536 KB Execution killed with signal 9
19 Correct 0 ms 344 KB Output is correct
20 Runtime error 188 ms 65536 KB Execution killed with signal 9
21 Correct 0 ms 344 KB Output is correct
22 Runtime error 203 ms 65536 KB Execution killed with signal 9
23 Correct 1 ms 348 KB Output is correct
24 Runtime error 191 ms 65536 KB Execution killed with signal 9
25 Correct 1 ms 344 KB Output is correct
26 Runtime error 200 ms 65536 KB Execution killed with signal 9
27 Correct 1 ms 344 KB Output is correct
28 Runtime error 193 ms 65536 KB Execution killed with signal 9
29 Correct 1 ms 348 KB Output is correct
30 Runtime error 189 ms 65536 KB Execution killed with signal 9
31 Correct 1 ms 348 KB Output is correct
32 Runtime error 229 ms 65536 KB Execution killed with signal 9
33 Correct 5 ms 1688 KB Output is correct
34 Runtime error 180 ms 65536 KB Execution killed with signal 9
35 Runtime error 183 ms 65536 KB Execution killed with signal 9
36 Correct 10 ms 1900 KB Output is correct
37 Runtime error 198 ms 65536 KB Execution killed with signal 9
38 Runtime error 203 ms 65536 KB Execution killed with signal 9
39 Correct 8 ms 2484 KB Output is correct
40 Runtime error 186 ms 65536 KB Execution killed with signal 9
41 Runtime error 183 ms 65536 KB Execution killed with signal 9
42 Correct 11 ms 2992 KB Output is correct
43 Runtime error 196 ms 65536 KB Execution killed with signal 9
44 Runtime error 197 ms 65536 KB Execution killed with signal 9
45 Correct 13 ms 3452 KB Output is correct
46 Runtime error 191 ms 65536 KB Execution killed with signal 9
47 Runtime error 183 ms 65536 KB Execution killed with signal 9
48 Correct 14 ms 4040 KB Output is correct
49 Runtime error 199 ms 65536 KB Execution killed with signal 9
50 Runtime error 183 ms 65536 KB Execution killed with signal 9
51 Correct 19 ms 4668 KB Output is correct
52 Runtime error 202 ms 65536 KB Execution killed with signal 9
53 Runtime error 188 ms 65536 KB Execution killed with signal 9
54 Correct 19 ms 5324 KB Output is correct
55 Runtime error 202 ms 65536 KB Execution killed with signal 9
56 Runtime error 186 ms 65536 KB Execution killed with signal 9
57 Correct 24 ms 6076 KB Output is correct
58 Runtime error 194 ms 65536 KB Execution killed with signal 9
59 Runtime error 186 ms 65536 KB Execution killed with signal 9
60 Correct 30 ms 6864 KB Output is correct
61 Runtime error 197 ms 65536 KB Execution killed with signal 9
62 Runtime error 208 ms 65536 KB Execution killed with signal 9
63 Runtime error 191 ms 65536 KB Execution killed with signal 9
64 Runtime error 188 ms 65536 KB Execution killed with signal 9
65 Runtime error 198 ms 65536 KB Execution killed with signal 9
66 Runtime error 227 ms 65536 KB Execution killed with signal 9
67 Runtime error 190 ms 65536 KB Execution killed with signal 9
68 Runtime error 195 ms 65536 KB Execution killed with signal 9
69 Runtime error 201 ms 65536 KB Execution killed with signal 9
70 Runtime error 197 ms 65536 KB Execution killed with signal 9
71 Runtime error 204 ms 65536 KB Execution killed with signal 9
72 Runtime error 178 ms 65536 KB Execution killed with signal 9
73 Runtime error 186 ms 65536 KB Execution killed with signal 9
74 Runtime error 153 ms 65536 KB Execution killed with signal 9
75 Runtime error 164 ms 65536 KB Execution killed with signal 9
76 Runtime error 146 ms 65536 KB Execution killed with signal 9
77 Runtime error 143 ms 65536 KB Execution killed with signal 9
78 Runtime error 144 ms 65536 KB Execution killed with signal 9
79 Runtime error 149 ms 65536 KB Execution killed with signal 9
80 Runtime error 162 ms 65536 KB Execution killed with signal 9
81 Runtime error 143 ms 65536 KB Execution killed with signal 9
82 Runtime error 152 ms 65536 KB Execution killed with signal 9
83 Runtime error 145 ms 65536 KB Execution killed with signal 9
84 Runtime error 169 ms 65536 KB Execution killed with signal 9
85 Runtime error 160 ms 65536 KB Execution killed with signal 9
86 Runtime error 154 ms 65536 KB Execution killed with signal 9
87 Runtime error 160 ms 65536 KB Execution killed with signal 9
88 Runtime error 148 ms 65536 KB Execution killed with signal 9
89 Runtime error 151 ms 65536 KB Execution killed with signal 9
90 Runtime error 156 ms 65536 KB Execution killed with signal 9
91 Runtime error 171 ms 65536 KB Execution killed with signal 9
92 Runtime error 146 ms 65536 KB Execution killed with signal 9