Submission #1082845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082845	2024-09-01T19:26:36 Z	v_matei	Mecho (IOI09_mecho)	C++17	20 / 100	1000 ms	65536 KB

mecho

#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::map<pii, int> d1, d2, d;

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::map<pii, 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});
      }
    }
  }
}

std::map<pii, bool> vis;
int ans = -1;

void dfs(pii nod, int k, int curr_min) {
  vis[nod] = 1;
  if (k % s == 0)
    curr_min = std::min(curr_min, abs(k / s + 1 - d2[nod]));

  if (nod == finish) {
    ans = std::max(ans, curr_min);
    // for (int i = 0; i <= k; i++)
    // std::cout << "{" << a[i].first << "," << a[i].second << "}" << ' ';
    // std::cout << '\n';
  }
  for (int i = 0; i < 4; i++) {
    pii nou = {nod.first + di[i], nod.second + dj[i]};
    if (!vis[nou] && d2[nou] * s > k + 1 && in(nou) &&
        map[nou.first][nou.second] != 'T') {
      dfs(nou, k + 1, curr_min);
    }
  }
  vis[nod] = 0;
}

int main() {
  std::cin.tie(0)->std::ios::sync_with_stdio(0);
  citire();

  std::queue<pii> q;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      d[{i, j}] = d1[{i, j}] = d2[{i, j}] = INF;
    }

  for (pii it : hives) {
    q.push(it);
    d2[it] = 0;
  }

  bfs(q, d2, [&](pii coords) {
    return in(coords) && map[coords.first][coords.second] != 'D' &&
           map[coords.first][coords.second] != 'T';
  });

  dfs(start, 0, INF);

  std::cout << ans << '\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

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	1 ms	348 KB	Output isn't correct
6	Incorrect	1 ms	348 KB	Output isn't correct
7	Runtime error	182 ms	65536 KB	Execution killed with signal 9
8	Correct	1 ms	348 KB	Output is correct
9	Execution timed out	1090 ms	348 KB	Time limit exceeded
10	Incorrect	55 ms	348 KB	Output isn't correct
11	Execution timed out	1043 ms	344 KB	Time limit exceeded
12	Correct	3 ms	1112 KB	Output is correct
13	Execution timed out	1035 ms	856 KB	Time limit exceeded
14	Execution timed out	1096 ms	1112 KB	Time limit exceeded
15	Correct	1 ms	348 KB	Output is correct
16	Incorrect	1 ms	604 KB	Output isn't correct
17	Correct	1 ms	604 KB	Output is correct
18	Incorrect	1 ms	616 KB	Output isn't correct
19	Correct	1 ms	604 KB	Output is correct
20	Incorrect	1 ms	756 KB	Output isn't correct
21	Correct	1 ms	860 KB	Output is correct
22	Incorrect	2 ms	860 KB	Output isn't correct
23	Correct	2 ms	1116 KB	Output is correct
24	Incorrect	3 ms	1132 KB	Output isn't correct
25	Correct	3 ms	1372 KB	Output is correct
26	Incorrect	4 ms	1372 KB	Output isn't correct
27	Correct	4 ms	1372 KB	Output is correct
28	Incorrect	5 ms	1880 KB	Output isn't correct
29	Correct	4 ms	1624 KB	Output is correct
30	Incorrect	6 ms	1884 KB	Output isn't correct
31	Correct	5 ms	1884 KB	Output is correct
32	Incorrect	7 ms	1956 KB	Output isn't correct
33	Correct	162 ms	31060 KB	Output is correct
34	Incorrect	195 ms	34936 KB	Output isn't correct
35	Execution timed out	1061 ms	35200 KB	Time limit exceeded
36	Correct	209 ms	40528 KB	Output is correct
37	Incorrect	277 ms	45396 KB	Output isn't correct
38	Execution timed out	1096 ms	45912 KB	Time limit exceeded
39	Correct	277 ms	51028 KB	Output is correct
40	Incorrect	338 ms	57272 KB	Output isn't correct
41	Execution timed out	1041 ms	57912 KB	Time limit exceeded
42	Correct	338 ms	62928 KB	Output is correct
43	Runtime error	282 ms	65536 KB	Execution killed with signal 9
44	Runtime error	433 ms	65536 KB	Execution killed with signal 9
45	Runtime error	275 ms	65536 KB	Execution killed with signal 9
46	Runtime error	265 ms	65536 KB	Execution killed with signal 9
47	Runtime error	494 ms	65536 KB	Execution killed with signal 9
48	Runtime error	180 ms	65536 KB	Execution killed with signal 9
49	Runtime error	169 ms	65536 KB	Execution killed with signal 9
50	Runtime error	185 ms	65536 KB	Execution killed with signal 9
51	Runtime error	181 ms	65536 KB	Execution killed with signal 9
52	Runtime error	179 ms	65536 KB	Execution killed with signal 9
53	Runtime error	178 ms	65536 KB	Execution killed with signal 9
54	Runtime error	186 ms	65536 KB	Execution killed with signal 9
55	Runtime error	181 ms	65536 KB	Execution killed with signal 9
56	Runtime error	182 ms	65536 KB	Execution killed with signal 9
57	Runtime error	176 ms	65536 KB	Execution killed with signal 9
58	Runtime error	180 ms	65536 KB	Execution killed with signal 9
59	Runtime error	180 ms	65536 KB	Execution killed with signal 9
60	Runtime error	180 ms	65536 KB	Execution killed with signal 9
61	Runtime error	175 ms	65536 KB	Execution killed with signal 9
62	Runtime error	182 ms	65536 KB	Execution killed with signal 9
63	Runtime error	186 ms	65536 KB	Execution killed with signal 9
64	Runtime error	177 ms	65536 KB	Execution killed with signal 9
65	Runtime error	178 ms	65536 KB	Execution killed with signal 9
66	Runtime error	186 ms	65536 KB	Execution killed with signal 9
67	Runtime error	170 ms	65536 KB	Execution killed with signal 9
68	Runtime error	185 ms	65536 KB	Execution killed with signal 9
69	Runtime error	188 ms	65536 KB	Execution killed with signal 9
70	Runtime error	180 ms	65536 KB	Execution killed with signal 9
71	Runtime error	183 ms	65536 KB	Execution killed with signal 9
72	Runtime error	193 ms	65536 KB	Execution killed with signal 9
73	Runtime error	204 ms	65536 KB	Execution killed with signal 9
74	Runtime error	193 ms	65536 KB	Execution killed with signal 9
75	Runtime error	189 ms	65536 KB	Execution killed with signal 9
76	Runtime error	183 ms	65536 KB	Execution killed with signal 9
77	Runtime error	195 ms	65536 KB	Execution killed with signal 9
78	Runtime error	178 ms	65536 KB	Execution killed with signal 9
79	Runtime error	172 ms	65536 KB	Execution killed with signal 9
80	Runtime error	175 ms	65536 KB	Execution killed with signal 9
81	Runtime error	183 ms	65536 KB	Execution killed with signal 9
82	Runtime error	175 ms	65536 KB	Execution killed with signal 9
83	Runtime error	175 ms	65536 KB	Execution killed with signal 9
84	Runtime error	181 ms	65536 KB	Execution killed with signal 9
85	Runtime error	181 ms	65536 KB	Execution killed with signal 9
86	Runtime error	178 ms	65536 KB	Execution killed with signal 9
87	Runtime error	176 ms	65536 KB	Execution killed with signal 9
88	Runtime error	187 ms	65536 KB	Execution killed with signal 9
89	Runtime error	184 ms	65536 KB	Execution killed with signal 9
90	Runtime error	188 ms	65536 KB	Execution killed with signal 9
91	Runtime error	181 ms	65536 KB	Execution killed with signal 9
92	Runtime error	182 ms	65536 KB	Execution killed with signal 9