제출 #953957

#제출 시각아이디문제언어결과실행 시간메모리
953957GithubMecho (IOI09_mecho)C++17
6 / 100
469 ms23076 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 ll MAXN = 810; ll bee[MAXN][MAXN]; ll dist[MAXN][MAXN]; pair<ll,ll> parent[MAXN][MAXN]; bool vis[MAXN][MAXN]; ll dX[] = {1, -1, 0, 0}; ll dY[] = {0, 0, 1, -1}; pair<ll, ll> mencho, den; vector<string> grid; ll n, s; bool compute(ll k){ for (ll i = 0; i < MAXN; i++){ for (ll j = 0; j < MAXN; j++){ dist[i][j] = 1e9; parent[i][j] = {-1, -1}; vis[i][j] = false; } } queue<pair<ll, ll>> q; q.push(mencho); dist[mencho.first][mencho.second] = 0; while (!q.empty()){ ll x = q.front().first, y = q.front().second; q.pop(); vis[x][y] = true; if (make_pair(x, y) == den){ break; } for (ll i = 0; i < 4; i++){ ll 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<ll, ll> cur = parent[den.first][den.second]; while (cur != make_pair((ll)-1, (ll)-1)){ if ((dist[cur.first][cur.second]/s) > bee[cur.first][cur.second]-k){ return false; } cur = parent[cur.first][cur.second]; } return true; } int main() { speedup cin >> n >> s; grid.resize(n); vector<pair<ll, ll>> start; for (ll i = 0; i < n; i++){ string st; cin >> st; grid[i] = st; for (ll 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 (ll i = 0; i < MAXN; i++){ for (ll j = 0; j < MAXN; j++){ bee[i][j] = 1e9; vis[i][j] = false; } } queue<pair<ll, ll>> q; for (pair<ll, ll> p: start){ bee[p.first][p.second] = 0; q.push({p.first, p.second}); } while (!q.empty()){ ll x = q.front().first, y = q.front().second; q.pop(); vis[x][y] = true; for (ll i = 0; i < 4; i++){ ll 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}); } } } ll l = 0, h = n*n, 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...