Submission #1082842

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082842	2024-09-01T19:23:42 Z	v_matei	Mecho (IOI09_mecho)	C++17	11 / 100	1000 ms	3676 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;
std::vector<pii> a(100, {0, 0});
int ans = -1;

void dfs(pii nod, int k, int curr_min) {
  vis[nod] = 1;
  a[k] = nod;
  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

11.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	1 ms	860 KB	Execution killed with signal 11
8	Correct	1 ms	348 KB	Output is correct
9	Execution timed out	1090 ms	348 KB	Time limit exceeded
10	Incorrect	63 ms	600 KB	Output isn't correct
11	Execution timed out	1043 ms	344 KB	Time limit exceeded
12	Correct	3 ms	1116 KB	Output is correct
13	Execution timed out	1099 ms	860 KB	Time limit exceeded
14	Execution timed out	1008 ms	1112 KB	Time limit exceeded
15	Runtime error	1 ms	860 KB	Execution killed with signal 6
16	Incorrect	1 ms	348 KB	Output isn't correct
17	Runtime error	1 ms	860 KB	Execution killed with signal 6
18	Runtime error	1 ms	860 KB	Execution killed with signal 6
19	Runtime error	1 ms	1116 KB	Execution killed with signal 6
20	Runtime error	2 ms	1112 KB	Execution killed with signal 6
21	Runtime error	3 ms	1300 KB	Execution killed with signal 6
22	Runtime error	3 ms	1368 KB	Execution killed with signal 6
23	Runtime error	3 ms	1884 KB	Execution killed with signal 6
24	Runtime error	4 ms	1884 KB	Execution killed with signal 6
25	Runtime error	4 ms	2440 KB	Execution killed with signal 6
26	Runtime error	5 ms	2652 KB	Execution killed with signal 6
27	Runtime error	5 ms	2652 KB	Execution killed with signal 6
28	Runtime error	6 ms	2908 KB	Execution killed with signal 6
29	Runtime error	6 ms	3004 KB	Execution killed with signal 6
30	Runtime error	7 ms	3388 KB	Execution killed with signal 6
31	Runtime error	6 ms	3332 KB	Execution killed with signal 6
32	Runtime error	9 ms	3676 KB	Execution killed with signal 6
33	Runtime error	1 ms	604 KB	Execution killed with signal 11
34	Runtime error	1 ms	604 KB	Execution killed with signal 11
35	Runtime error	1 ms	600 KB	Execution killed with signal 11
36	Runtime error	1 ms	600 KB	Execution killed with signal 11
37	Runtime error	1 ms	604 KB	Execution killed with signal 11
38	Runtime error	1 ms	604 KB	Execution killed with signal 11
39	Runtime error	1 ms	596 KB	Execution killed with signal 11
40	Runtime error	1 ms	604 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	860 KB	Execution killed with signal 11
46	Runtime error	1 ms	860 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	2 ms	856 KB	Execution killed with signal 11
50	Runtime error	1 ms	860 KB	Execution killed with signal 11
51	Runtime error	2 ms	860 KB	Execution killed with signal 11
52	Runtime error	2 ms	860 KB	Execution killed with signal 11
53	Runtime error	2 ms	1000 KB	Execution killed with signal 11
54	Runtime error	1 ms	856 KB	Execution killed with signal 11
55	Runtime error	1 ms	860 KB	Execution killed with signal 11
56	Runtime error	1 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	856 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	1 ms	860 KB	Execution killed with signal 11
65	Runtime error	1 ms	736 KB	Execution killed with signal 11
66	Runtime error	1 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	740 KB	Execution killed with signal 11
69	Runtime error	1 ms	860 KB	Execution killed with signal 11
70	Runtime error	2 ms	860 KB	Execution killed with signal 11
71	Runtime error	1 ms	860 KB	Execution killed with signal 11
72	Runtime error	1 ms	860 KB	Execution killed with signal 11
73	Runtime error	2 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	848 KB	Execution killed with signal 11
77	Runtime error	2 ms	860 KB	Execution killed with signal 11
78	Runtime error	1 ms	856 KB	Execution killed with signal 11
79	Runtime error	2 ms	856 KB	Execution killed with signal 11
80	Runtime error	1 ms	860 KB	Execution killed with signal 11
81	Runtime error	1 ms	860 KB	Execution killed with signal 11
82	Runtime error	1 ms	860 KB	Execution killed with signal 11
83	Runtime error	1 ms	860 KB	Execution killed with signal 11
84	Runtime error	1 ms	860 KB	Execution killed with signal 11
85	Runtime error	1 ms	860 KB	Execution killed with signal 11
86	Runtime error	1 ms	860 KB	Execution killed with signal 11
87	Runtime error	1 ms	860 KB	Execution killed with signal 11
88	Runtime error	1 ms	844 KB	Execution killed with signal 11
89	Runtime error	2 ms	860 KB	Execution killed with signal 11
90	Runtime error	1 ms	840 KB	Execution killed with signal 11
91	Runtime error	2 ms	860 KB	Execution killed with signal 11
92	Runtime error	1 ms	860 KB	Execution killed with signal 11