oj.uz

Submission #1088626

# Submission time Handle Problem Language Result Execution time Memory
1088626 2024-09-14T17:17:57 Z v_matei Mecho (IOI09_mecho) C++17
31 / 100
 226 ms 14044 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);
    bfs2(q, d, [&](pii coords) {
      return in(coords) && map[coords.first][coords.second] != 'H' &&
             map[coords.first][coords.second] != 'T';
    });
    
    if (d[finish.first][finish.second] != INF) {
      ok = 1;
      return true;
    } else {
      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 Correct 8 ms 12184 KB Output is correct
2 Correct 11 ms 12196 KB Output is correct
3 Correct 9 ms 12204 KB Output is correct
4 Correct 9 ms 12248 KB Output is correct
5 Incorrect 10 ms 12224 KB Output isn't correct
6 Correct 13 ms 12244 KB Output is correct
7 Correct 108 ms 13780 KB Output is correct
8 Correct 11 ms 12244 KB Output is correct
9 Incorrect 11 ms 12364 KB Output isn't correct
10 Incorrect 11 ms 12244 KB Output isn't correct
11 Incorrect 11 ms 12244 KB Output isn't correct
12 Incorrect 17 ms 12444 KB Output isn't correct
13 Incorrect 16 ms 12400 KB Output isn't correct
14 Correct 16 ms 12428 KB Output is correct
15 Correct 14 ms 12284 KB Output is correct
16 Correct 13 ms 12284 KB Output is correct
17 Correct 13 ms 12344 KB Output is correct
18 Incorrect 14 ms 12280 KB Output isn't correct
19 Correct 15 ms 12304 KB Output is correct
20 Incorrect 13 ms 12384 KB Output isn't correct
21 Correct 14 ms 12304 KB Output is correct
22 Correct 15 ms 12324 KB Output is correct
23 Correct 15 ms 12412 KB Output is correct
24 Incorrect 16 ms 12376 KB Output isn't correct
25 Correct 17 ms 12420 KB Output is correct
26 Correct 16 ms 12400 KB Output is correct
27 Correct 16 ms 12420 KB Output is correct
28 Incorrect 19 ms 12436 KB Output isn't correct
29 Correct 16 ms 12480 KB Output is correct
30 Incorrect 19 ms 12440 KB Output isn't correct
31 Correct 16 ms 12448 KB Output is correct
32 Correct 17 ms 12412 KB Output is correct
33 Correct 27 ms 12892 KB Output is correct
34 Incorrect 43 ms 12804 KB Output isn't correct
35 Incorrect 47 ms 12712 KB Output isn't correct
36 Correct 30 ms 12928 KB Output is correct
37 Correct 29 ms 12992 KB Output is correct
38 Incorrect 57 ms 12952 KB Output isn't correct
39 Correct 30 ms 13040 KB Output is correct
40 Incorrect 61 ms 13004 KB Output isn't correct
41 Incorrect 74 ms 13084 KB Output isn't correct
42 Correct 30 ms 13132 KB Output is correct
43 Correct 35 ms 13076 KB Output is correct
44 Incorrect 73 ms 13068 KB Output isn't correct
45 Correct 34 ms 13256 KB Output is correct
46 Incorrect 89 ms 13216 KB Output isn't correct
47 Incorrect 96 ms 13184 KB Output isn't correct
48 Correct 37 ms 13320 KB Output is correct
49 Correct 39 ms 13336 KB Output is correct
50 Incorrect 91 ms 13340 KB Output isn't correct
51 Correct 43 ms 13472 KB Output is correct
52 Incorrect 119 ms 13360 KB Output isn't correct
53 Incorrect 122 ms 13440 KB Output isn't correct
54 Correct 47 ms 13600 KB Output is correct
55 Correct 43 ms 13564 KB Output is correct
56 Incorrect 117 ms 13584 KB Output isn't correct
57 Correct 52 ms 13720 KB Output is correct
58 Incorrect 150 ms 13588 KB Output isn't correct
59 Incorrect 147 ms 13676 KB Output isn't correct
60 Correct 55 ms 13784 KB Output is correct
61 Correct 56 ms 13800 KB Output is correct
62 Incorrect 175 ms 13820 KB Output isn't correct
63 Incorrect 127 ms 13772 KB Output isn't correct
64 Correct 226 ms 13776 KB Output is correct
65 Incorrect 211 ms 13764 KB Output isn't correct
66 Correct 152 ms 13780 KB Output is correct
67 Correct 145 ms 13744 KB Output is correct
68 Incorrect 78 ms 13844 KB Output isn't correct
69 Incorrect 79 ms 13840 KB Output isn't correct
70 Correct 70 ms 13836 KB Output is correct
71 Correct 65 ms 13892 KB Output is correct
72 Incorrect 95 ms 13776 KB Output isn't correct
73 Incorrect 67 ms 13848 KB Output isn't correct
74 Incorrect 146 ms 13880 KB Output isn't correct
75 Incorrect 109 ms 13716 KB Output isn't correct
76 Correct 93 ms 13808 KB Output is correct
77 Incorrect 125 ms 13792 KB Output isn't correct
78 Correct 118 ms 14044 KB Output is correct
79 Correct 86 ms 13884 KB Output is correct
80 Correct 104 ms 13868 KB Output is correct
81 Correct 110 ms 13844 KB Output is correct
82 Incorrect 134 ms 13868 KB Output isn't correct
83 Incorrect 124 ms 13836 KB Output isn't correct
84 Correct 110 ms 13884 KB Output is correct
85 Incorrect 111 ms 13788 KB Output isn't correct
86 Incorrect 104 ms 13876 KB Output isn't correct
87 Correct 116 ms 13840 KB Output is correct
88 Incorrect 117 ms 13804 KB Output isn't correct
89 Correct 132 ms 13804 KB Output is correct
90 Correct 122 ms 13748 KB Output is correct
91 Incorrect 146 ms 13804 KB Output isn't correct
92 Correct 120 ms 13836 KB Output is correct