oj.uz

Submission #1088632

# Submission time Handle Problem Language Result Execution time Memory
1088632 2024-09-14T17:25:24 Z v_matei Mecho (IOI09_mecho) C++17
31 / 100
 209 ms 26676 KB 
#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");

#define NMAX 1000
#define INF INT_MAX

int n, s;
char map[NMAX][NMAX];
pii start, finish;
std::vector<pii> hives;
std::vector<std::vector<int>> d1(NMAX, std::vector<int>(NMAX, INF)),
    d2(NMAX, std::vector<int>(NMAX, INF));

int di[]{1, -1, 0, 0}, dj[]{0, 0, 1, -1};

void citire() {
  std::cin >> n >> s;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      std::cin >> map[i][j];
      if (map[i][j] == 'M')
        start = {i, j};
      if (map[i][j] == 'D')
        finish = {i, j};
      if (map[i][j] == 'H')
        hives.push_back({i, j});
    }
}

bool in(pii coord) {
  int i = coord.first, j = coord.second;
  return i >= 0 && i < n && j >= 0 && j < n;
}

void bfs(std::queue<pii> &q, std::vector<std::vector<int>> &d,
         std::function<bool(pii coords)> check) {
  while (!q.empty()) {
    pii u = q.front();
    int i = u.first;
    int j = u.second;
    q.pop();

    for (int k = 0; k < 4; k++) {
      int ni = i + di[k];
      int nj = j + dj[k];
      if (check({ni, nj}) && d[ni][nj] > d[i][j] + 1) {
        d[ni][nj] = d[i][j] + 1;
        q.push({ni, nj});
      }
    }
  }
}
void bfs2(std::queue<pii> &q, std::vector<std::vector<int>> &d,
          std::function<bool(pii coords)> check) {
  while (!q.empty()) {
    pii u = q.front();
    int i = u.first;
    int j = u.second;
    q.pop();

    for (int k = 0; k < 4; k++) {
      int ni = i + di[k];
      int nj = j + dj[k];
      if (check({ni, nj}) && d[ni][nj] > d[i][j] + 1) {
        if (d[i][j] + 1 < s * d2[ni][nj]) {
          d[ni][nj] = d[i][j] + 1;
          q.push({ni, nj});
        }
      }
    }
  }
}

int b_search(int l, int r, std::function<bool(int)> f) {
  while (r > l + 1) {
    int mid = (r + l) / 2;
    if (f(mid))
      l = mid;
    else
      r = mid;
  }
  return l;
}

int ok = 0;

int main() {
  std::cin.tie(0)->std::ios::sync_with_stdio(0);
  citire();

  std::queue<pii> q;

  for (pii it : hives) {
    q.push(it);
    d2[it.first][it.second] = 0;
  }

  bfs(q, d2, [&](pii coords) {
    return in(coords) && map[coords.first][coords.second] != 'D' &&
           map[coords.first][coords.second] != 'T';
  });
  int ans = b_search(0, n * n, [&](int w) {
    std::vector<std::vector<int>> d(NMAX, std::vector<int>(NMAX, INF));
    d[start.first][start.second] = w * s;
    q.push(start);
    if (w >= d2[start.first][start.second])
      q.pop();
    bfs2(q, d, [&](pii coords) {
      return in(coords) && map[coords.first][coords.second] != 'H' &&
             map[coords.first][coords.second] != 'T';
    });

    for (int k = 0; k < 4; k++) {
      if (d[finish.first+di[k]][finish.second+dj[k]] != INF) {
        ok = 1;
        return true;
      }
    }
    return false;
  });

  if (ok) {
    std::cout << ans << '\n';
  } else
    std::cout << -1 << '\n';
  /*for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (d2[i][j] != INF)
        std::cout << d2[i][j] << ' ';
      else
        std::cout << "oo ";
    }
    std::cout << '\n';
  }*/
  return 0;
}

Subtask #1
31.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 24664 KB Execution killed with signal 11
2 Runtime error 14 ms 24668 KB Execution killed with signal 11
3 Runtime error 21 ms 24500 KB Execution killed with signal 11
4 Runtime error 14 ms 24664 KB Execution killed with signal 11
5 Incorrect 11 ms 12224 KB Output isn't correct
6 Correct 12 ms 12352 KB Output is correct
7 Incorrect 49 ms 13688 KB Output isn't correct
8 Correct 12 ms 12244 KB Output is correct
9 Correct 12 ms 12364 KB Output is correct
10 Correct 13 ms 12264 KB Output is correct
11 Correct 12 ms 12264 KB Output is correct
12 Runtime error 14 ms 24576 KB Execution killed with signal 11
13 Incorrect 16 ms 12396 KB Output isn't correct
14 Correct 16 ms 12412 KB Output is correct
15 Runtime error 14 ms 24504 KB Execution killed with signal 11
16 Correct 16 ms 12376 KB Output is correct
17 Runtime error 20 ms 24664 KB Execution killed with signal 11
18 Correct 15 ms 12304 KB Output is correct
19 Runtime error 13 ms 24628 KB Execution killed with signal 11
20 Correct 14 ms 12352 KB Output is correct
21 Runtime error 19 ms 24924 KB Execution killed with signal 11
22 Correct 16 ms 12324 KB Output is correct
23 Runtime error 14 ms 24664 KB Execution killed with signal 11
24 Correct 15 ms 12400 KB Output is correct
25 Runtime error 14 ms 24668 KB Execution killed with signal 11
26 Correct 23 ms 12400 KB Output is correct
27 Runtime error 16 ms 24668 KB Execution killed with signal 11
28 Correct 18 ms 12420 KB Output is correct
29 Runtime error 14 ms 24764 KB Execution killed with signal 11
30 Correct 20 ms 12436 KB Output is correct
31 Runtime error 14 ms 24664 KB Execution killed with signal 11
32 Correct 20 ms 12440 KB Output is correct
33 Runtime error 18 ms 25436 KB Execution killed with signal 11
34 Correct 25 ms 12896 KB Output is correct
35 Correct 44 ms 12848 KB Output is correct
36 Runtime error 19 ms 25436 KB Execution killed with signal 11
37 Correct 29 ms 12968 KB Output is correct
38 Correct 49 ms 12864 KB Output is correct
39 Runtime error 18 ms 25692 KB Execution killed with signal 11
40 Correct 29 ms 13064 KB Output is correct
41 Correct 62 ms 13052 KB Output is correct
42 Runtime error 19 ms 25680 KB Execution killed with signal 11
43 Correct 30 ms 13188 KB Output is correct
44 Correct 69 ms 13076 KB Output is correct
45 Runtime error 20 ms 25948 KB Execution killed with signal 11
46 Correct 33 ms 13252 KB Output is correct
47 Correct 75 ms 13232 KB Output is correct
48 Runtime error 21 ms 26060 KB Execution killed with signal 11
49 Correct 34 ms 13280 KB Output is correct
50 Correct 100 ms 13292 KB Output is correct
51 Runtime error 23 ms 26216 KB Execution killed with signal 11
52 Correct 37 ms 13436 KB Output is correct
53 Correct 105 ms 13380 KB Output is correct
54 Runtime error 24 ms 26416 KB Execution killed with signal 11
55 Correct 46 ms 13564 KB Output is correct
56 Correct 133 ms 13568 KB Output is correct
57 Runtime error 26 ms 26448 KB Execution killed with signal 11
58 Correct 41 ms 13572 KB Output is correct
59 Correct 131 ms 13656 KB Output is correct
60 Runtime error 31 ms 26676 KB Execution killed with signal 11
61 Correct 52 ms 13736 KB Output is correct
62 Correct 161 ms 13712 KB Output is correct
63 Incorrect 116 ms 13620 KB Output isn't correct
64 Correct 209 ms 13564 KB Output is correct
65 Correct 175 ms 13568 KB Output is correct
66 Correct 141 ms 13572 KB Output is correct
67 Correct 135 ms 13624 KB Output is correct
68 Incorrect 68 ms 13728 KB Output isn't correct
69 Correct 73 ms 13724 KB Output is correct
70 Correct 67 ms 13732 KB Output is correct
71 Correct 66 ms 13728 KB Output is correct
72 Correct 54 ms 13672 KB Output is correct
73 Correct 60 ms 13776 KB Output is correct
74 Correct 81 ms 13760 KB Output is correct
75 Correct 95 ms 13696 KB Output is correct
76 Correct 89 ms 13724 KB Output is correct
77 Correct 95 ms 13652 KB Output is correct
78 Correct 114 ms 13852 KB Output is correct
79 Correct 74 ms 13732 KB Output is correct
80 Correct 82 ms 13724 KB Output is correct
81 Correct 91 ms 13740 KB Output is correct
82 Correct 82 ms 13684 KB Output is correct
83 Incorrect 53 ms 13676 KB Output isn't correct
84 Incorrect 58 ms 13704 KB Output isn't correct
85 Incorrect 55 ms 13772 KB Output isn't correct
86 Incorrect 50 ms 14012 KB Output isn't correct
87 Incorrect 49 ms 13764 KB Output isn't correct
88 Incorrect 49 ms 13748 KB Output isn't correct
89 Incorrect 49 ms 13784 KB Output isn't correct
90 Incorrect 49 ms 13704 KB Output isn't correct
91 Incorrect 51 ms 13680 KB Output isn't correct
92 Incorrect 53 ms 13724 KB Output isn't correct