Submission #953953

#TimeUsernameProblemLanguageResultExecution timeMemory
953953GithubMecho (IOI09_mecho)C++17
22 / 100
497 ms12884 KiB
#include <iostream> #include <vector> #include <queue> #include <cstring> #include <map> #include <climits> #include <cmath> #include <algorithm> #include <stack> using namespace std; #define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define ll long long const int MAXN = 810; int bee[MAXN][MAXN]; int dist[MAXN][MAXN]; pair<int,int> parent[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dX[] = {1, -1, 0, 0}; int dY[] = {0, 0, 1, -1}; pair<int, int> mencho, den; vector<string> grid; int n, s; bool compute(int k){ for (int i = 0; i < MAXN; i++){ for (int j = 0; j < MAXN; j++){ dist[i][j] = 1e9; parent[i][j] = {-1, -1}; vis[i][j] = false; } } queue<pair<int, int>> q; q.push(mencho); dist[mencho.first][mencho.second] = 0; while (!q.empty()){ int x = q.front().first, y = q.front().second; q.pop(); vis[x][y] = true; for (int i = 0; i < 4; i++){ int nX = x + dX[i], nY = y+dY[i]; if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H'){ continue; } if (dist[nX][nY] > dist[x][y]+1 && !vis[nX][nY]){ dist[nX][nY] = dist[x][y]+1; parent[nX][nY] = {x, y}; q.push({nX, nY}); } } } pair<int, int> cur = den; while (cur != make_pair(-1, -1)){ if (k+(int)(dist[cur.first][cur.second]+s-1)/s > bee[cur.first][cur.second]){ return false; } cur = parent[cur.first][cur.second]; } return true; } int main() { speedup cin >> n >> s; grid.resize(n); vector<pair<int, int>> start; for (int i = 0; i < n; i++){ string st; cin >> st; grid[i] = st; for (int j = 0; j < n; j++){ if (st[j] == 'H'){ start.push_back({i, j}); }else if (st[j] == 'M'){ mencho = {i, j}; }else if (st[j] == 'D'){ den = {i, j}; } } } for (int i = 0; i < MAXN; i++){ for (int j = 0; j < MAXN; j++){ bee[i][j] = 1e9; vis[i][j] = false; } } queue<pair<int, int>> q; for (pair<int, int> p: start){ bee[p.first][p.second] = 0; q.push({p.first, p.second}); } while (!q.empty()){ int x = q.front().first, y = q.front().second; q.pop(); vis[x][y] = true; for (int i = 0; i < 4; i++){ int nX = x + dX[i], nY = y+dY[i]; if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'D'){ continue; } if (bee[nX][nY] > bee[x][y]+1 && !vis[nX][nY]){ bee[nX][nY] = bee[x][y]+1; q.push({nX, nY}); } } } int l = 0, h = 1e9, mid, ans = -1; while (l <= h){ mid = (l+h)/2; if (compute(mid)){ ans = mid; l = mid+1; }else{ h = mid-1; } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...