Submission #1208569

#TimeUsernameProblemLanguageResultExecution timeMemory
1208569timeflewMecho (IOI09_mecho)C++20
23 / 100
1096 ms16388 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 805; int n, s; char c[MAX_N][MAX_N]; vector<vector<int>> vis(MAX_N, vector<int>(MAX_N, INT_MAX)); // bee_time pair<int, int> st, ed; // Start 'M' and end 'D' positions int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; // BFS to compute when bees reach each cell void compute_bee_times() { queue<pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (c[i][j] == 'H') { q.push({i, j}); vis[i][j] = 0; } } } while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx >= 0 && nx < n && ny >= 0 && ny < n && (c[nx][ny] == 'G' || c[nx][ny] == 'M') && vis[nx][ny] == INT_MAX) { vis[nx][ny] = vis[x][y] + 1; q.push({nx, ny}); } } } } // Check if Mecho can reach 'D' starting at minute k+1 bool check(int k) { if (vis[st.first][st.second] <= k) return false; // Caught at 'M' vector<pair<int, int>> current_positions; queue<array<int, 3>> q; // (x, y, dist) vector<vector<bool>> local_vis(n, vector<bool>(n, false)); q.push({st.first, st.second, 0}); local_vis[st.first][st.second] = true; // Positions reachable at the end of minute k+1 while (!q.empty()) { auto [x, y, dist] = q.front(); q.pop(); if (dist > s) continue; if (vis[x][y] > k + 1) { current_positions.push_back({x, y}); } for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx >= 0 && nx < n && ny >= 0 && ny < n && c[nx][ny] != 'T' && c[nx][ny] != 'H' && !local_vis[nx][ny]) { local_vis[nx][ny] = true; q.push({nx, ny, dist + 1}); } } } int t = k + 1; while (!current_positions.empty()) { if (find(current_positions.begin(), current_positions.end(), ed) != current_positions.end()) { return true; } t++; vector<pair<int, int>> next_positions; q = queue<array<int, 3>>(); local_vis.assign(n, vector<bool>(n, false)); // Start BFS from all current positions for (auto [x, y] : current_positions) { if (!local_vis[x][y]) { q.push({x, y, 0}); local_vis[x][y] = true; } } // Positions reachable by the end of minute t while (!q.empty()) { auto [x, y, dist] = q.front(); q.pop(); if (dist > s) continue; if (vis[x][y] > t) { next_positions.push_back({x, y}); } for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx >= 0 && nx < n && ny >= 0 && ny < n && c[nx][ny] != 'T' && c[nx][ny] != 'H' && !local_vis[nx][ny]) { local_vis[nx][ny] = true; q.push({nx, ny, dist + 1}); } } } current_positions = next_positions; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> s; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> c[i][j]; if (c[i][j] == 'M') st = {i, j}; if (c[i][j] == 'D') ed = {i, j}; } } compute_bee_times(); int lo = 0, hi = n * n; // Maximum reasonable k int ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (check(mid)) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...