Submission #309482

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
309482	2020-10-03 15:30:13	Temmie	Mecho (IOI09_mecho)	C++17	100 / 100	262 ms	6352 KiB

mecho

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
int n, s;
std::vector <std::string> g;
std::vector <std::vector <int>> bee;
bool ff(int val) {
  std::vector <std::vector <int>> bear(n, std::vector <int> (n, 1e9));
  int endX, endY;
  std::queue <std::pair <int, int>> q;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (g[i][j] == 'D') endX = j, endY = i;
      if (g[i][j] == 'M') {
        bear[i][j] = 0;
        q.push({ j, i });
      }
    }
  }
  if (val >= bee[q.front().second][q.front().first]) return false;
  while (q.size()) {
    auto now = q.front(); q.pop();
    int x = now.first, y = now.second;
    if (x + 1 >= 0 && y >= 0 && x + 1 < n && y < n && g[y][x + 1] != 'T' && bear[y][x + 1] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y][x + 1]) q.push({ x + 1, y }), bear[y][x + 1] = bear[y][x] + 1;
    if (x >= 0 && y + 1 >= 0 && x < n && y + 1 < n && g[y + 1][x] != 'T' && bear[y + 1][x] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y + 1][x]) q.push({ x, y + 1 }), bear[y + 1][x] = bear[y][x] + 1;
    if (x - 1 >= 0 && y >= 0 && x - 1 < n && y < n && g[y][x - 1] != 'T' && bear[y][x - 1] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y][x - 1]) q.push({ x - 1, y }), bear[y][x - 1] = bear[y][x] + 1;
    if (x >= 0 && y - 1 >= 0 && x < n && y - 1 < n && g[y - 1][x] != 'T' && bear[y - 1][x] == int(1e9) && ((bear[y][x] + 1) / s) + val < bee[y - 1][x]) q.push({ x, y - 1 }), bear[y - 1][x] = bear[y][x] + 1;
  }
  return bear[endY][endX] < int(1e9);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

mecho.cpp: In function 'bool ff(int)':
mecho.cpp:29:18: warning: 'endY' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |  return bear[endY][endX] < int(1e9);
      |                  ^
mecho.cpp:29:24: warning: 'endX' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |  return bear[endY][endX] < int(1e9);
      |                        ^

• Subtask 1: 100 / 100