Submission #1072480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072480		7again	Mecho (IOI09_mecho)	C++17	100 / 100	432 ms	11440 KiB

mecho

#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 ;
}

• Subtask 1: 100 / 100