Submission #1154329

#TimeUsernameProblemLanguageResultExecution timeMemory
1154329i_liek_cheezitsMecho (IOI09_mecho)C++20
11 / 100
264 ms6488 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define f first #define s second #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } const int INF = (int)1e9; const int MAXN = 805; const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; string grid[MAXN]; int dist[MAXN][MAXN], prev_dist[MAXN][MAXN]; pii start; vector<pii> hives; struct Entry { pii p; int dist; int timer; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, s; cin >> n >> s; for(int i = 0; i < n; i++) { cin >> grid[i]; for(int j = 0; j < n; j++) { prev_dist[i][j] = INF; if (grid[i][j] == 'M') { prev_dist[i][j] = 0; start = {i, j}; } if (grid[i][j] == 'H') { prev_dist[i][j] = 0; hives.push_back({i, j}); } } } int l = 0, r = 3000; queue<pii> q; while(l < r) { int m = (l+r+1)/2; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) dist[i][j] = prev_dist[i][j]; } for(pii &x : hives) q.push(x); while(sz(q)) { pii p = q.front(); q.pop(); for(int i = 0; i < 4; i++) { pii np = {p.f + dx[i], p.s + dy[i]}; if (np.f >= 0 && np.s >= 0 && np.f < n && np.s < n && grid[np.f][np.s] != 'T' && grid[np.f][np.s] != 'D' && ckmin(dist[np.f][np.s], dist[p.f][p.s]+1)) { q.push(np); } } } bool ok = false; queue<Entry> q2; q2.push({start, 0, 0}); while(sz(q2)) { auto [p, d, t] = q2.front(); q2.pop(); if (grid[p.f][p.s] == 'D') { ok = true; break; } for(int i = 0; i < 4; i++) { pii np = {p.f + dx[i], p.s + dy[i]}; if (np.f >= 0 && np.s >= 0 && np.f < n && np.s < n && grid[np.f][np.s] != 'T' && ckmin(dist[np.f][np.s], d + m - 1 + (t == 0))) { if (t) { q2.push({np, d, --t}); } else { q2.push({np, d+1, s}); } } } } if (ok) l = m; else r = m-1; } cout << l << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...