제출 #1224110

#제출 시각아이디문제언어결과실행 시간메모리
1224110firegirlwaterboyMecho (IOI09_mecho)C++20
34 / 100
519 ms6828 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; int n, s; vector<string> grid; bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && (grid[x][y] == 'G' || grid[x][y] == 'M'); } bool reached(int mdis, int bdis) { return mdis / s < bdis; } int main() { cin >> n >> s; grid.resize(n); for (int i = 0; i < n; i++) { cin >> grid[i]; } vector<pii> hives; int mx, my, hx, hy; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 'M') { mx = i, my = j; } else if (grid[i][j] == 'H') { hives.push_back({i, j}); } else if (grid[i][j] == 'D') { hx = i, hy = j; } } } auto ok = [&](int x) { vector<vector<bool>> bvis(n, vector<bool>(n)), mvis(n, vector<bool>(n)); vector<vector<int>> btime(n, vector<int>(n)), mtime(n, vector<int>(n)); queue<pii> q; for (auto i : hives) { q.push({i.first, i.second}); bvis[i.first][i.second] = true; } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (valid(nx, ny) && !bvis[nx][ny]) { btime[nx][ny] = btime[x][y] + 1; q.push({nx, ny}); bvis[nx][ny] = true; } } } q.push({mx, my}); mvis[mx][my] = true; if (btime[mx][my] <= x) { q.pop(); } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (valid(nx, ny) && !mvis[nx][ny] && reached(mtime[x][y] + 1, btime[nx][ny] - x)) { mvis[nx][ny] = true; q.push({nx, ny}); mtime[nx][ny] = mtime[x][y] + 1; } } } bool tmp = false; for (int i = 0; i < 4; i++) { int nx = hx + dx[i], ny = hy + dy[i]; if (valid(nx, ny) && reached(mtime[nx][ny], btime[nx][ny] - x) && mvis[nx][ny]) { tmp = true; } } return tmp; }; int l = 0, r = n * n, ans; while (l <= r) { int mid = (l + r) / 2; if (ok(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...