Submission #309482

#TimeUsernameProblemLanguageResultExecution timeMemory
309482TemmieMecho (IOI09_mecho)C++17
100 / 100
262 ms6352 KiB
#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); } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cin >> n >> s; g.resize(n); for (auto& x : g) std::cin >> x; bee.resize(n, std::vector <int> (n, 1e9)); 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] == 'H') { q.push({ j, i }); bee[i][j] = 0; } } } 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 && bee[y][x + 1] == int(1e9) && g[y][x + 1] != 'T' && g[y][x + 1] != 'D') q.push({ x + 1, y }), bee[y][x + 1] = bee[y][x] + 1; if (x >= 0 && y + 1 >= 0 && x < n && y + 1 < n && bee[y + 1][x] == int(1e9) && g[y + 1][x] != 'T' && g[y + 1][x] != 'D') q.push({ x, y + 1 }), bee[y + 1][x] = bee[y][x] + 1; if (x - 1 >= 0 && y >= 0 && x - 1 < n && y < n && bee[y][x - 1] == int(1e9) && g[y][x - 1] != 'T' && g[y][x - 1] != 'D') q.push({ x - 1, y }), bee[y][x - 1] = bee[y][x] + 1; if (x >= 0 && y - 1 >= 0 && x < n && y - 1 < n && bee[y - 1][x] == int(1e9) && g[y - 1][x] != 'T' && g[y - 1][x] != 'D') q.push({ x, y - 1 }), bee[y - 1][x] = bee[y][x] + 1; } int l = -1, r = n * n; while (l + 1 < r) { int mid = (l + r) >> 1; if (ff(mid)) l = mid; else r = mid; } std::cout << l << "\n"; }

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);
      |                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...