oj.uz

Submission #511162

# Submission time Handle Problem Language Result Execution time Memory
511162 2022-01-15T10:01:31 Z 600Mihnea Mecho (IOI09_mecho) C++17
30 / 100
 157 ms 16660 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int n;
int speed;
int r1, c1;
int r2, c2;
int a[N][N];
int dist_m[N][N];
int dist_b[N][N];

vector<pair<int, int>> ord;

void compute(int dist[N][N], vector<pair<int, int>> init) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dist[i][j] = INF;
    }
  }

  queue<pair<int, int>> q;
  for (auto &it : init) {
    dist[it.first][it.second] = 0;
    q.push(it);
  }
  while (!q.empty()) {
    auto it = q.front();
    int r = it.first;
    int c = it.second;
    ord.push_back(it);
    q.pop();
    for (int k = 0; k < 4; k++) {
      int rn = r + dr[k];
      int cn = c + dc[k];
      if (a[rn][cn] && dist[rn][cn] == INF) {
        dist[rn][cn] = 1 + dist[r][c];
        q.push({rn, cn});
      }
    }
  }
}

int dist[N][N];
bool ok[N][N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

 /// freopen ("input", "r", stdin);

  cin >> n >> speed;

  vector<pair<int, int>> bees;

  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 1; j <= n; j++) {
      char ch = s[j - 1];
      if (ch == 'T') {
        a[i][j] = 0;
        continue;
      }
      if (ch == 'G') {
        a[i][j] = 1;
        continue;
      }
      if (ch == 'M') {
        r1 = i;
        c1 = j;
        a[i][j] = 1;
        continue;
      }
      if (ch == 'D') {
        r2 = i;
        c2 = j;
        a[i][j] = 1;
        continue;
      }
      if (ch == 'H') {
        bees.push_back({i, j});
        continue;
      }
    }
  }
  vector<pair<int, int>> m;
  m.push_back({r1, c1});
  compute(dist_b, bees);
  ord.clear();
  compute(dist_m, m);

  int low = 0, high = dist_b[r1][c1], sol = -1;

  while (low <= high) {
    int stay = (low + high) / 2;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        ok[i][j] = 0;
      }
    }
    ok[r1][c1] = 1;
    for (auto &it : ord) {
      if (ok[it.first][it.second]) {
        int r = it.first, c = it.second;
        for (int k = 0; k < 4; k++) {
          int rn = r + dr[k];
          int cn = c + dc[k];
          ok[rn][cn] |= (stay + (dist_m[rn][cn] + speed - 1) / speed <= dist_b[rn][cn]);
        }
      }
    }
    if (ok[r2][c2]) {
      sol = stay;
      low = stay + 1;
    } else {
      high = stay - 1;
    }
  }

  cout << sol << "\n";
  return 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int val = dist_m[i][j];
      if (val == INF) {
        cout << "- ";
      } else {
        cout << val << " ";
      }
    }
    cout << "\n";
  }

  return 0;
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Incorrect 0 ms 324 KB Output isn't correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Correct 0 ms 328 KB Output is correct
6 Incorrect 0 ms 448 KB Output isn't correct
7 Incorrect 97 ms 16304 KB Output isn't correct
8 Incorrect 1 ms 452 KB Output isn't correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Incorrect 1 ms 1100 KB Output isn't correct
13 Incorrect 1 ms 972 KB Output isn't correct
14 Correct 1 ms 1100 KB Output is correct
15 Incorrect 1 ms 588 KB Output isn't correct
16 Correct 1 ms 584 KB Output is correct
17 Incorrect 1 ms 588 KB Output isn't correct
18 Correct 1 ms 584 KB Output is correct
19 Incorrect 1 ms 692 KB Output isn't correct
20 Correct 1 ms 716 KB Output is correct
21 Incorrect 1 ms 844 KB Output isn't correct
22 Correct 1 ms 836 KB Output is correct
23 Incorrect 1 ms 972 KB Output isn't correct
24 Correct 1 ms 956 KB Output is correct
25 Incorrect 1 ms 1100 KB Output isn't correct
26 Correct 1 ms 1100 KB Output is correct
27 Incorrect 1 ms 1228 KB Output isn't correct
28 Correct 1 ms 1100 KB Output is correct
29 Incorrect 1 ms 1224 KB Output isn't correct
30 Correct 1 ms 1228 KB Output is correct
31 Incorrect 1 ms 1356 KB Output isn't correct
32 Correct 1 ms 1356 KB Output is correct
33 Incorrect 7 ms 5496 KB Output isn't correct
34 Correct 7 ms 5452 KB Output is correct
35 Incorrect 12 ms 5704 KB Output isn't correct
36 Incorrect 10 ms 6256 KB Output isn't correct
37 Correct 10 ms 6268 KB Output is correct
38 Incorrect 22 ms 6600 KB Output isn't correct
39 Incorrect 12 ms 7236 KB Output isn't correct
40 Correct 11 ms 7244 KB Output is correct
41 Incorrect 22 ms 7616 KB Output isn't correct
42 Incorrect 15 ms 8060 KB Output isn't correct
43 Correct 15 ms 8056 KB Output is correct
44 Incorrect 27 ms 8644 KB Output isn't correct
45 Incorrect 16 ms 9032 KB Output isn't correct
46 Correct 17 ms 9036 KB Output is correct
47 Incorrect 32 ms 9544 KB Output isn't correct
48 Incorrect 22 ms 9904 KB Output isn't correct
49 Correct 18 ms 9920 KB Output is correct
50 Incorrect 41 ms 10564 KB Output isn't correct
51 Incorrect 21 ms 10796 KB Output isn't correct
52 Correct 22 ms 10844 KB Output is correct
53 Incorrect 46 ms 11712 KB Output isn't correct
54 Incorrect 26 ms 11796 KB Output isn't correct
55 Correct 26 ms 11952 KB Output is correct
56 Incorrect 54 ms 12788 KB Output isn't correct
57 Incorrect 34 ms 12772 KB Output isn't correct
58 Correct 36 ms 12856 KB Output is correct
59 Incorrect 62 ms 13864 KB Output isn't correct
60 Incorrect 31 ms 13760 KB Output isn't correct
61 Correct 31 ms 13784 KB Output is correct
62 Incorrect 72 ms 15056 KB Output isn't correct
63 Correct 106 ms 14296 KB Output is correct
64 Correct 157 ms 14336 KB Output is correct
65 Correct 143 ms 14260 KB Output is correct
66 Incorrect 126 ms 14352 KB Output isn't correct
67 Correct 119 ms 14352 KB Output is correct
68 Correct 65 ms 14256 KB Output is correct
69 Correct 57 ms 14256 KB Output is correct
70 Correct 60 ms 14352 KB Output is correct
71 Correct 52 ms 14308 KB Output is correct
72 Incorrect 54 ms 14368 KB Output isn't correct
73 Incorrect 52 ms 16532 KB Output isn't correct
74 Correct 75 ms 16544 KB Output is correct
75 Correct 84 ms 16532 KB Output is correct
76 Correct 88 ms 16552 KB Output is correct
77 Correct 115 ms 16524 KB Output is correct
78 Correct 84 ms 16440 KB Output is correct
79 Correct 53 ms 16436 KB Output is correct
80 Correct 71 ms 16476 KB Output is correct
81 Correct 88 ms 16660 KB Output is correct
82 Correct 95 ms 16488 KB Output is correct
83 Correct 97 ms 16412 KB Output is correct
84 Correct 76 ms 16420 KB Output is correct
85 Correct 71 ms 16328 KB Output is correct
86 Correct 88 ms 16324 KB Output is correct
87 Correct 95 ms 16400 KB Output is correct
88 Correct 128 ms 16308 KB Output is correct
89 Correct 123 ms 16368 KB Output is correct
90 Correct 130 ms 16248 KB Output is correct
91 Correct 103 ms 16296 KB Output is correct
92 Correct 99 ms 16392 KB Output is correct