답안 #1112354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112354	2024-11-14T06:21:47 Z	greenbinjack	Mecho (IOI09_mecho)	C++17	22 / 100	255 ms	9456 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 + 1, 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

22.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is 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	9404 KB	Output isn't correct
8	Correct	1 ms	336 KB	Output is 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	592 KB	Output isn't correct
13	Correct	1 ms	764 KB	Output is correct
14	Correct	1 ms	592 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Incorrect	1 ms	336 KB	Output isn't correct
17	Correct	1 ms	336 KB	Output is correct
18	Incorrect	1 ms	336 KB	Output isn't correct
19	Correct	1 ms	592 KB	Output is correct
20	Incorrect	1 ms	592 KB	Output isn't correct
21	Correct	1 ms	592 KB	Output is correct
22	Incorrect	1 ms	592 KB	Output isn't correct
23	Correct	1 ms	592 KB	Output is correct
24	Incorrect	1 ms	592 KB	Output isn't correct
25	Correct	1 ms	592 KB	Output is correct
26	Incorrect	1 ms	592 KB	Output isn't correct
27	Correct	1 ms	592 KB	Output is correct
28	Incorrect	2 ms	592 KB	Output isn't correct
29	Correct	2 ms	760 KB	Output is correct
30	Incorrect	1 ms	592 KB	Output isn't correct
31	Correct	2 ms	592 KB	Output is correct
32	Incorrect	1 ms	592 KB	Output isn't correct
33	Correct	14 ms	2944 KB	Output is correct
34	Incorrect	15 ms	2960 KB	Output isn't correct
35	Incorrect	26 ms	2960 KB	Output isn't correct
36	Correct	18 ms	3384 KB	Output is correct
37	Incorrect	21 ms	3536 KB	Output isn't correct
38	Incorrect	35 ms	3536 KB	Output isn't correct
39	Correct	23 ms	4224 KB	Output is correct
40	Incorrect	30 ms	4104 KB	Output isn't correct
41	Incorrect	43 ms	4088 KB	Output isn't correct
42	Correct	36 ms	4700 KB	Output is correct
43	Incorrect	29 ms	4700 KB	Output isn't correct
44	Incorrect	62 ms	4700 KB	Output isn't correct
45	Correct	39 ms	5376 KB	Output is correct
46	Incorrect	37 ms	5376 KB	Output isn't correct
47	Incorrect	72 ms	5372 KB	Output isn't correct
48	Correct	41 ms	6128 KB	Output is correct
49	Incorrect	42 ms	6096 KB	Output isn't correct
50	Incorrect	87 ms	6080 KB	Output isn't correct
51	Correct	75 ms	6412 KB	Output is correct
52	Incorrect	50 ms	7008 KB	Output isn't correct
53	Incorrect	90 ms	6808 KB	Output isn't correct
54	Correct	62 ms	7640 KB	Output is correct
55	Incorrect	53 ms	7404 KB	Output isn't correct
56	Incorrect	136 ms	7636 KB	Output isn't correct
57	Correct	87 ms	7928 KB	Output is correct
58	Incorrect	67 ms	8476 KB	Output isn't correct
59	Incorrect	132 ms	8480 KB	Output isn't correct
60	Correct	83 ms	9280 KB	Output is correct
61	Incorrect	81 ms	9252 KB	Output isn't correct
62	Incorrect	185 ms	9232 KB	Output isn't correct
63	Incorrect	144 ms	9280 KB	Output isn't correct
64	Incorrect	214 ms	9328 KB	Output isn't correct
65	Incorrect	255 ms	8708 KB	Output isn't correct
66	Correct	215 ms	9368 KB	Output is correct
67	Correct	191 ms	9420 KB	Output is correct
68	Incorrect	105 ms	9288 KB	Output isn't correct
69	Incorrect	121 ms	9296 KB	Output isn't correct
70	Incorrect	98 ms	8752 KB	Output isn't correct
71	Incorrect	98 ms	9408 KB	Output isn't correct
72	Correct	104 ms	9268 KB	Output is correct
73	Correct	82 ms	9272 KB	Output is correct
74	Incorrect	109 ms	9380 KB	Output isn't correct
75	Incorrect	107 ms	9272 KB	Output isn't correct
76	Incorrect	112 ms	9412 KB	Output isn't correct
77	Incorrect	130 ms	9304 KB	Output isn't correct
78	Correct	153 ms	9412 KB	Output is correct
79	Incorrect	100 ms	9316 KB	Output isn't correct
80	Incorrect	107 ms	9408 KB	Output isn't correct
81	Incorrect	126 ms	9428 KB	Output isn't correct
82	Incorrect	109 ms	9392 KB	Output isn't correct
83	Incorrect	207 ms	9340 KB	Output isn't correct
84	Incorrect	138 ms	9416 KB	Output isn't correct
85	Incorrect	120 ms	8796 KB	Output isn't correct
86	Incorrect	159 ms	9412 KB	Output isn't correct
87	Incorrect	129 ms	9456 KB	Output isn't correct
88	Incorrect	125 ms	9396 KB	Output isn't correct
89	Incorrect	142 ms	9288 KB	Output isn't correct
90	Incorrect	139 ms	9416 KB	Output isn't correct
91	Incorrect	128 ms	8808 KB	Output isn't correct
92	Incorrect	126 ms	9428 KB	Output isn't correct