oj.uz

Submission #511163

# Submission time Handle Problem Language Result Execution time Memory
511163 2022-01-15T10:10:31 Z 600Mihnea Mecho (IOI09_mecho) C++17
19 / 100
 130 ms 15948 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]);
        }
      }
    }
   /* for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          cout << (stay + (dist_m[i][j] + speed - 1) / speed) << " ";
        } else {
          cout << "- ";
        }
        ///cout << ok[i][j] << " ";
      }
      cout << "\n";
    }
    cout << "\n";

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          cout << dist_b[i][j] << " ";
        } else {
          cout << "- ";
        }
        ///cout << ok[i][j] << " ";
      }
      cout << "\n";
    }

    exit(0);*/

    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
19.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Incorrect 0 ms 332 KB Output isn't correct
6 Incorrect 1 ms 460 KB Output isn't correct
7 Incorrect 104 ms 15684 KB Output isn't correct
8 Correct 0 ms 460 KB Output is correct
9 Incorrect 0 ms 460 KB Output isn't correct
10 Incorrect 0 ms 460 KB Output isn't correct
11 Incorrect 1 ms 460 KB Output isn't correct
12 Incorrect 1 ms 1100 KB Output isn't correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 0 ms 588 KB Output is correct
16 Incorrect 0 ms 588 KB Output isn't correct
17 Correct 0 ms 588 KB Output is correct
18 Incorrect 1 ms 588 KB Output isn't correct
19 Correct 1 ms 716 KB Output is correct
20 Incorrect 1 ms 716 KB Output isn't correct
21 Correct 1 ms 844 KB Output is correct
22 Incorrect 1 ms 844 KB Output isn't correct
23 Correct 1 ms 972 KB Output is correct
24 Incorrect 1 ms 972 KB Output isn't correct
25 Correct 1 ms 1100 KB Output is correct
26 Incorrect 1 ms 1100 KB Output isn't correct
27 Correct 1 ms 1100 KB Output is correct
28 Incorrect 1 ms 1100 KB Output isn't correct
29 Correct 1 ms 1228 KB Output is correct
30 Incorrect 1 ms 1228 KB Output isn't correct
31 Correct 1 ms 1228 KB Output is correct
32 Incorrect 1 ms 1356 KB Output isn't correct
33 Correct 7 ms 5452 KB Output is correct
34 Incorrect 8 ms 5324 KB Output isn't correct
35 Incorrect 13 ms 5596 KB Output isn't correct
36 Correct 9 ms 6240 KB Output is correct
37 Incorrect 11 ms 6216 KB Output isn't correct
38 Incorrect 15 ms 6472 KB Output isn't correct
39 Correct 12 ms 7004 KB Output is correct
40 Incorrect 11 ms 6980 KB Output isn't correct
41 Incorrect 19 ms 7360 KB Output isn't correct
42 Correct 14 ms 7880 KB Output is correct
43 Incorrect 18 ms 7792 KB Output isn't correct
44 Incorrect 22 ms 8260 KB Output isn't correct
45 Correct 15 ms 8720 KB Output is correct
46 Incorrect 15 ms 8708 KB Output isn't correct
47 Incorrect 27 ms 9212 KB Output isn't correct
48 Correct 19 ms 9536 KB Output is correct
49 Incorrect 17 ms 9536 KB Output isn't correct
50 Incorrect 34 ms 10232 KB Output isn't correct
51 Correct 22 ms 10468 KB Output is correct
52 Incorrect 27 ms 10428 KB Output isn't correct
53 Incorrect 38 ms 11200 KB Output isn't correct
54 Correct 26 ms 11328 KB Output is correct
55 Incorrect 24 ms 11308 KB Output isn't correct
56 Incorrect 48 ms 12280 KB Output isn't correct
57 Correct 31 ms 12220 KB Output is correct
58 Incorrect 30 ms 12220 KB Output isn't correct
59 Incorrect 70 ms 13336 KB Output isn't correct
60 Correct 31 ms 13164 KB Output is correct
61 Incorrect 31 ms 13240 KB Output isn't correct
62 Incorrect 67 ms 14400 KB Output isn't correct
63 Incorrect 91 ms 13712 KB Output isn't correct
64 Incorrect 126 ms 13704 KB Output isn't correct
65 Incorrect 130 ms 13692 KB Output isn't correct
66 Correct 123 ms 13716 KB Output is correct
67 Correct 111 ms 13712 KB Output is correct
68 Incorrect 64 ms 13752 KB Output isn't correct
69 Incorrect 54 ms 13616 KB Output isn't correct
70 Incorrect 56 ms 13720 KB Output isn't correct
71 Incorrect 53 ms 13664 KB Output isn't correct
72 Correct 51 ms 13736 KB Output is correct
73 Correct 44 ms 15880 KB Output is correct
74 Incorrect 75 ms 15892 KB Output isn't correct
75 Incorrect 81 ms 15948 KB Output isn't correct
76 Incorrect 78 ms 15812 KB Output isn't correct
77 Incorrect 89 ms 15892 KB Output isn't correct
78 Correct 82 ms 15920 KB Output is correct
79 Incorrect 54 ms 15836 KB Output isn't correct
80 Incorrect 66 ms 15832 KB Output isn't correct
81 Incorrect 90 ms 15872 KB Output isn't correct
82 Incorrect 63 ms 15900 KB Output isn't correct
83 Incorrect 83 ms 15796 KB Output isn't correct
84 Incorrect 83 ms 15784 KB Output isn't correct
85 Incorrect 70 ms 15768 KB Output isn't correct
86 Incorrect 100 ms 15772 KB Output isn't correct
87 Incorrect 84 ms 15788 KB Output isn't correct
88 Incorrect 88 ms 15800 KB Output isn't correct
89 Incorrect 91 ms 15724 KB Output isn't correct
90 Incorrect 99 ms 15748 KB Output isn't correct
91 Incorrect 94 ms 15784 KB Output isn't correct
92 Incorrect 118 ms 15748 KB Output isn't correct