Submission #1082844

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082844	2024-09-01T19:25:36 Z	v_matei	Mecho (IOI09_mecho)	C++17	20 / 100	1000 ms	1884 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 100
#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	0 ms	348 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	0 ms	348 KB	Output isn't correct
6	Incorrect	1 ms	348 KB	Output isn't correct
7	Runtime error	2 ms	856 KB	Execution killed with signal 11
8	Correct	1 ms	348 KB	Output is correct
9	Execution timed out	1099 ms	348 KB	Time limit exceeded
10	Incorrect	63 ms	348 KB	Output isn't correct
11	Execution timed out	1092 ms	604 KB	Time limit exceeded
12	Correct	3 ms	1112 KB	Output is correct
13	Execution timed out	1073 ms	860 KB	Time limit exceeded
14	Execution timed out	1022 ms	1112 KB	Time limit exceeded
15	Correct	1 ms	344 KB	Output is correct
16	Incorrect	1 ms	348 KB	Output isn't correct
17	Correct	1 ms	604 KB	Output is correct
18	Incorrect	1 ms	604 KB	Output isn't correct
19	Correct	1 ms	604 KB	Output is correct
20	Incorrect	1 ms	604 KB	Output isn't correct
21	Correct	2 ms	860 KB	Output is correct
22	Incorrect	2 ms	860 KB	Output isn't correct
23	Correct	2 ms	860 KB	Output is correct
24	Incorrect	3 ms	1116 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	1476 KB	Output is correct
28	Incorrect	5 ms	1628 KB	Output isn't correct
29	Correct	4 ms	1628 KB	Output is correct
30	Incorrect	5 ms	1628 KB	Output isn't correct
31	Correct	5 ms	1884 KB	Output is correct
32	Incorrect	7 ms	1884 KB	Output isn't correct
33	Runtime error	1 ms	604 KB	Execution killed with signal 11
34	Runtime error	1 ms	600 KB	Execution killed with signal 11
35	Runtime error	1 ms	604 KB	Execution killed with signal 11
36	Runtime error	1 ms	604 KB	Execution killed with signal 11
37	Runtime error	2 ms	1112 KB	Execution killed with signal 11
38	Runtime error	1 ms	604 KB	Execution killed with signal 11
39	Runtime error	1 ms	604 KB	Execution killed with signal 11
40	Runtime error	1 ms	584 KB	Execution killed with signal 11
41	Runtime error	1 ms	604 KB	Execution killed with signal 11
42	Runtime error	1 ms	860 KB	Execution killed with signal 11
43	Runtime error	1 ms	860 KB	Execution killed with signal 11
44	Runtime error	1 ms	860 KB	Execution killed with signal 11
45	Runtime error	1 ms	684 KB	Execution killed with signal 11
46	Runtime error	1 ms	732 KB	Execution killed with signal 11
47	Runtime error	1 ms	860 KB	Execution killed with signal 11
48	Runtime error	1 ms	860 KB	Execution killed with signal 11
49	Runtime error	1 ms	860 KB	Execution killed with signal 11
50	Runtime error	1 ms	860 KB	Execution killed with signal 11
51	Runtime error	1 ms	860 KB	Execution killed with signal 11
52	Runtime error	1 ms	860 KB	Execution killed with signal 11
53	Runtime error	1 ms	860 KB	Execution killed with signal 11
54	Runtime error	1 ms	860 KB	Execution killed with signal 11
55	Runtime error	1 ms	860 KB	Execution killed with signal 11
56	Runtime error	2 ms	860 KB	Execution killed with signal 11
57	Runtime error	1 ms	860 KB	Execution killed with signal 11
58	Runtime error	1 ms	860 KB	Execution killed with signal 11
59	Runtime error	1 ms	860 KB	Execution killed with signal 11
60	Runtime error	2 ms	860 KB	Execution killed with signal 11
61	Runtime error	2 ms	860 KB	Execution killed with signal 11
62	Runtime error	1 ms	860 KB	Execution killed with signal 11
63	Runtime error	2 ms	860 KB	Execution killed with signal 11
64	Runtime error	3 ms	716 KB	Execution killed with signal 11
65	Runtime error	1 ms	860 KB	Execution killed with signal 11
66	Runtime error	2 ms	860 KB	Execution killed with signal 11
67	Runtime error	1 ms	860 KB	Execution killed with signal 11
68	Runtime error	1 ms	860 KB	Execution killed with signal 11
69	Runtime error	2 ms	856 KB	Execution killed with signal 11
70	Runtime error	1 ms	860 KB	Execution killed with signal 11
71	Runtime error	1 ms	840 KB	Execution killed with signal 11
72	Runtime error	1 ms	860 KB	Execution killed with signal 11
73	Runtime error	1 ms	860 KB	Execution killed with signal 11
74	Runtime error	1 ms	860 KB	Execution killed with signal 11
75	Runtime error	1 ms	860 KB	Execution killed with signal 11
76	Runtime error	1 ms	860 KB	Execution killed with signal 11
77	Runtime error	1 ms	860 KB	Execution killed with signal 11
78	Runtime error	2 ms	856 KB	Execution killed with signal 11
79	Runtime error	1 ms	860 KB	Execution killed with signal 11
80	Runtime error	1 ms	720 KB	Execution killed with signal 11
81	Runtime error	1 ms	860 KB	Execution killed with signal 11
82	Runtime error	2 ms	860 KB	Execution killed with signal 11
83	Runtime error	1 ms	860 KB	Execution killed with signal 11
84	Runtime error	2 ms	860 KB	Execution killed with signal 11
85	Runtime error	1 ms	860 KB	Execution killed with signal 11
86	Runtime error	2 ms	856 KB	Execution killed with signal 11
87	Runtime error	2 ms	860 KB	Execution killed with signal 11
88	Runtime error	1 ms	768 KB	Execution killed with signal 11
89	Runtime error	2 ms	860 KB	Execution killed with signal 11
90	Runtime error	2 ms	860 KB	Execution killed with signal 11
91	Runtime error	1 ms	736 KB	Execution killed with signal 11
92	Runtime error	1 ms	860 KB	Execution killed with signal 11