제출 #1072480

#제출 시각아이디문제언어결과실행 시간메모리
10724807againMecho (IOI09_mecho)C++17
100 / 100
432 ms11440 KiB
#include <bits/stdc++.h> using namespace std ; const int N = 801 ; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; int n , s ; pair <int , int> Honey , Home ; char a[N][N] ; bool inside(int x , int y) { return (x >= 0 && y >= 0 && x < n && y < n && (a[x][y] == 'G' || a[x][y] == 'M')) ; } bool val(int x , int y) { return x / s < y ; } int ok(int time) { int mn2[n + 4][n + 4] ; int vis2[n + 4][n + 4] ; fill_n(&mn2[0][0] , (n + 4) * (n + 4) , 1e9) ; fill_n(&vis2[0][0] , (n + 4) * (n + 4) , 0) ; queue<pair <int , int>> q2 ; for(int i = 0 ; i < n ; i++) { for(int j = 0 ; j < n ; j++) { if(a[i][j] == 'H') { q2.push({i, j}) ; mn2[i][j] = 0 ; vis2[i][j] = 1 ; } } } while(q2.size()) { pair <int , int> t = q2.front() ; q2.pop() ; for(int i = 0 ; i < 4 ; i++) { int x = t.first + dx[i] ; int y = t.second + dy[i] ; if(inside(x , y) && mn2[t.first][t.second] + 1 < mn2[x][y] && !vis2[x][y]) { mn2[x][y] = mn2[t.first][t.second] + 1 ; q2.push({x, y}) ; vis2[x][y] = 1 ; } } } int mn[n + 4][n + 4] ; int vis[n + 4][n + 4] ; fill_n(&mn[0][0] , (n + 4) * (n + 4) , 1e9 ) ; fill_n(&vis[0][0] , (n + 4) * (n + 4) , 0) ; queue <pair <int , int>> q ; mn[Honey.first][Honey.second] = 0 ; vis[Honey.first][Honey.second] = 1 ; if(mn2[Honey.first][Honey.second] > time) q.push(Honey) ; while(!q.empty()) { pair <int , int> t = q.front() ; q.pop() ; for(int i = 0 ; i < 4 ; i++) { int x = t.first + dx[i] ; int y = t.second + dy[i] ; if(inside(x , y) && val(mn[t.first][t.second] + 1 , mn2[x][y] - time) && mn[t.first][t.second] + 1 < mn[x][y] && !vis[x][y]) { mn[x][y] = mn[t.first][t.second] + 1 ; q.push({x , y}) ; vis[x][y] = 1 ; } } } for(int i = 0 ; i < 4 ; i++){ int x = Home.first + dx[i] ; int y = Home.second + dy[i] ; if(inside(x , y) && vis[x][y] && val(mn[x][y] , mn2[x][y] - time)) return true ; } return false ; } int main() { cin >> n >> s ; for(int i = 0 ; i < n ; i++) { for(int j = 0 ; j < n ; j++) { cin >> a[i][j] ; if(a[i][j] == 'M') Honey = {i , j} ; if(a[i][j] == 'D') Home = {i , j} ; } } int l = 0 , r = n * n + 4 ; while(l <= r) { int m = l + (r - l) / 2 ; if(ok(m)) l = m + 1 ; else r = m - 1 ; } cout << l - 1 << endl ; }
#Verdict Execution timeMemoryGrader output
Fetching results...