Submission #1112346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112346	2024-11-14T06:06:24 Z	greenbinjack	Mecho (IOI09_mecho)	C++17	4 / 100	232 ms	8840 KB

mecho

#include <bits/stdc++.h>
using namespace std;

#define all(V) V.begin(), V.end()
#define x first
#define y second

using LL = long long;

const int N = 808;

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

char grid[N][N];  
int n, k, bees[N][N];
pair <int, int> start, finish;

bool valid (int i, int j) {
  return (i > 0 and i <= n and j > 0 and j <= n);
}

bool check (int Time) {
  queue < pair <int, int> > q;
  q.push (start);
  vector < vector < pair <int, int> > > dist (n + 1, vector < pair <int, int> > (n + 1, {INT_MAX, 0}));
  dist[start.x][start.y] = {Time, 0};
  while (!q.empty ()) {
    auto [X, Y] = q.front ();
    q.pop ();
    for (int i = 0; i < 4; i++) {
      int nwX = X + dx[i], nwY = Y + dy[i];
      if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'D')) {
        if (dist[X][Y].x + (dist[X][Y].y == k) < dist[nwX][nwY].x and dist[X][Y].x + (dist[X][Y].y == k) <= bees[nwX][nwY]) {
          if (dist[X][Y].y == k) dist[nwX][nwY] = {dist[X][Y].x + 1, 1};
          else dist[nwX][nwY] = {dist[X][Y].x, dist[X][Y].y + 1};
          q.push ({nwX, nwY});
        }
      }
    }
  }
  return dist[finish.x][finish.y].x != INT_MAX;
}

int main() {
  cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> grid[i][j];
      if (grid[i][j] == 'M') start = {i, j};
      if (grid[i][j] == 'D') finish = {i, j};
    }
  }
  
  queue < pair <int, int> > q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (grid[i][j] == 'H') {
        q.push ({i, j});
        bees[i][j] = 0;
      } else {
        bees[i][j] = INT_MAX;
      }
    }
  }

  while (!q.empty ()) {
    auto [X, Y] = q.front ();
    q.pop ();
    for (int i = 0; i < 4; i++) {
      int nwX = X + dx[i], nwY = Y + dy[i];
      if (!valid (nwX, nwY)) continue;
      if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'M') and bees[X][Y] + 1 < bees[nwX][nwY]) {
        bees[nwX][nwY] = bees[X][Y] + 1;
        q.push ({nwX, nwY});
      }
    }
  }

  int left = 0, right = n * n;
  while (left < right) {
    int mid = (left + right + 1) >> 1;
    if (check (mid)) left = mid;  
    else right = mid - 1;
  }

  if (!check (left)) left--;

  cout << left << '\n';

  return 0;
}

Subtask #1

4.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output isn't correct
2	Incorrect	1 ms	336 KB	Output isn't correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Incorrect	1 ms	336 KB	Output isn't correct
5	Incorrect	1 ms	336 KB	Output isn't correct
6	Incorrect	1 ms	336 KB	Output isn't correct
7	Incorrect	124 ms	8592 KB	Output isn't correct
8	Incorrect	1 ms	336 KB	Output isn't correct
9	Incorrect	1 ms	336 KB	Output isn't correct
10	Incorrect	1 ms	336 KB	Output isn't correct
11	Incorrect	1 ms	336 KB	Output isn't correct
12	Incorrect	1 ms	2640 KB	Output isn't correct
13	Incorrect	1 ms	592 KB	Output isn't correct
14	Correct	1 ms	2640 KB	Output is correct
15	Incorrect	1 ms	336 KB	Output isn't correct
16	Incorrect	1 ms	336 KB	Output isn't correct
17	Incorrect	1 ms	336 KB	Output isn't correct
18	Incorrect	2 ms	336 KB	Output isn't correct
19	Incorrect	1 ms	592 KB	Output isn't correct
20	Incorrect	1 ms	592 KB	Output isn't correct
21	Incorrect	1 ms	524 KB	Output isn't correct
22	Incorrect	1 ms	592 KB	Output isn't correct
23	Incorrect	1 ms	592 KB	Output isn't correct
24	Incorrect	1 ms	592 KB	Output isn't correct
25	Incorrect	1 ms	2640 KB	Output isn't correct
26	Incorrect	1 ms	2640 KB	Output isn't correct
27	Incorrect	1 ms	2640 KB	Output isn't correct
28	Incorrect	1 ms	2640 KB	Output isn't correct
29	Incorrect	1 ms	2640 KB	Output isn't correct
30	Incorrect	1 ms	2640 KB	Output isn't correct
31	Incorrect	1 ms	2640 KB	Output isn't correct
32	Incorrect	1 ms	2640 KB	Output isn't correct
33	Incorrect	16 ms	3936 KB	Output isn't correct
34	Incorrect	14 ms	3936 KB	Output isn't correct
35	Incorrect	27 ms	3936 KB	Output isn't correct
36	Incorrect	18 ms	4272 KB	Output isn't correct
37	Incorrect	18 ms	4320 KB	Output isn't correct
38	Incorrect	35 ms	4304 KB	Output isn't correct
39	Incorrect	23 ms	4000 KB	Output isn't correct
40	Incorrect	22 ms	3904 KB	Output isn't correct
41	Incorrect	48 ms	3868 KB	Output isn't correct
42	Incorrect	29 ms	4512 KB	Output isn't correct
43	Incorrect	28 ms	4444 KB	Output isn't correct
44	Incorrect	55 ms	4496 KB	Output isn't correct
45	Incorrect	34 ms	5096 KB	Output isn't correct
46	Incorrect	33 ms	5076 KB	Output isn't correct
47	Incorrect	66 ms	5088 KB	Output isn't correct
48	Incorrect	45 ms	5744 KB	Output isn't correct
49	Incorrect	43 ms	5904 KB	Output isn't correct
50	Incorrect	83 ms	6016 KB	Output isn't correct
51	Incorrect	49 ms	6668 KB	Output isn't correct
52	Incorrect	52 ms	6516 KB	Output isn't correct
53	Incorrect	104 ms	6416 KB	Output isn't correct
54	Incorrect	59 ms	7144 KB	Output isn't correct
55	Incorrect	55 ms	7200 KB	Output isn't correct
56	Incorrect	125 ms	7160 KB	Output isn't correct
57	Incorrect	61 ms	7980 KB	Output isn't correct
58	Incorrect	62 ms	7956 KB	Output isn't correct
59	Incorrect	132 ms	7936 KB	Output isn't correct
60	Incorrect	72 ms	8744 KB	Output isn't correct
61	Incorrect	70 ms	8816 KB	Output isn't correct
62	Incorrect	180 ms	8756 KB	Output isn't correct
63	Incorrect	156 ms	8720 KB	Output isn't correct
64	Incorrect	232 ms	8744 KB	Output isn't correct
65	Incorrect	188 ms	8744 KB	Output isn't correct
66	Incorrect	168 ms	8768 KB	Output isn't correct
67	Correct	156 ms	8720 KB	Output is correct
68	Incorrect	101 ms	8728 KB	Output isn't correct
69	Incorrect	96 ms	8752 KB	Output isn't correct
70	Incorrect	97 ms	8800 KB	Output isn't correct
71	Incorrect	93 ms	8784 KB	Output isn't correct
72	Incorrect	80 ms	8820 KB	Output isn't correct
73	Incorrect	88 ms	8804 KB	Output isn't correct
74	Incorrect	99 ms	8768 KB	Output isn't correct
75	Incorrect	108 ms	8768 KB	Output isn't correct
76	Incorrect	111 ms	8784 KB	Output isn't correct
77	Incorrect	106 ms	8768 KB	Output isn't correct
78	Correct	124 ms	8760 KB	Output is correct
79	Incorrect	100 ms	8752 KB	Output isn't correct
80	Incorrect	110 ms	8776 KB	Output isn't correct
81	Incorrect	111 ms	8840 KB	Output isn't correct
82	Incorrect	101 ms	8736 KB	Output isn't correct
83	Incorrect	113 ms	8748 KB	Output isn't correct
84	Incorrect	107 ms	8788 KB	Output isn't correct
85	Incorrect	122 ms	8748 KB	Output isn't correct
86	Incorrect	123 ms	8784 KB	Output isn't correct
87	Incorrect	113 ms	8808 KB	Output isn't correct
88	Incorrect	121 ms	8784 KB	Output isn't correct
89	Incorrect	126 ms	8836 KB	Output isn't correct
90	Incorrect	118 ms	8752 KB	Output isn't correct
91	Incorrect	122 ms	8772 KB	Output isn't correct
92	Incorrect	123 ms	8776 KB	Output isn't correct