Submission #1101372

#TimeUsernameProblemLanguageResultExecution timeMemory
1101372jadai007Mecho (IOI09_mecho)C++17
23 / 100
134 ms9236 KiB
#include<bits/stdc++.h> using namespace std; int n, s, disH[1010][1010], dis[1010][1010], xx[] = {0, 0, -1, 1}, xy[] = {-1, 1, 0, 0}; char mp[1010][1010]; queue<tuple<int, int, int>> q; bool solve(int mid){ for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n; ++j){ if(mp[i][j] == 'M') q.emplace(i, j, 0), dis[i][j] = 0; else dis[i][j] = 1e9; } } while(!q.empty()){ int x = get<0>(q.front()), y = get<1>(q.front()), w = get<2>(q.front()); q.pop(); if(dis[x][y] < w || (dis[x][y] + 1) / s >= disH[x][y] - mid) continue; if(mp[x][y] == 'D') return true; for(int i = 0; i < 4; ++i){ int nx = x + xx[i]; int ny = y + xy[i]; if(nx < 1 || nx > n || ny < 1 || ny > n || mp[nx][ny] == 'T') continue; if(dis[nx][ny] > w + 1){ dis[nx][ny] = w + 1; q.emplace(nx, ny, w + 1); } } } return false; } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> s; for(int i = 1; i<=n; ++i) for(int j = 1; j <= n; ++j) cin >> mp[i][j]; for(int i = 1; i <= n; ++i){ for(int j = 1; j <=n; ++j){ if(mp[i][j] == 'H') q.emplace(i, j, 0), disH[i][j] = 0; else disH[i][j] = 1e9; } } while(!q.empty()){ int x = get<0>(q.front()), y = get<1>(q.front()), w = get<2>(q.front()); q.pop(); if(disH[x][y] < w) continue; for(int i = 0; i < 4; ++i){ int nx = x + xx[i]; int ny = y + xy[i]; if(nx < 1 || nx > n || ny < 1 || ny > n || mp[nx][ny] == 'T') continue; if(disH[nx][ny] > w + 1){ disH[nx][ny] = w + 1; q.emplace(nx, ny, w + 1); } } } int l = 0, r = 1e9, ans = -1; while(l <= r){ int mid = (l + r) >> 1; if(solve(mid)) ans = mid, l = mid + 1; else r = mid - 1; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...