Submission #1185267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185267		prism7k	Mecho (IOI09_mecho)	C++20	13 / 100	142 ms	6616 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
 
char grid[800][800];
int bee_dist[800][800];
int bear_dist[800][800];
bool vis_dfs[800][800];
const int INF = 2000000005;
 
vector<pair<int,int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
 
int main(){
    pair<int,int> bear_start;
    pair<int,int> end;
    int n,s; cin >> n >> s;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            bee_dist[i][j] = bear_dist[i][j] = INF;
        }
    }
    queue<pair<int,int>> q1, q2;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> grid[i][j];
            if(grid[i][j]=='M'){
                q1.push({i,j});
                bear_dist[i][j] = 0;
                bear_start = {i,j};
            } else if(grid[i][j]=='H'){
                q2.push({i,j});
                bee_dist[i][j] = 0;
            } else if(grid[i][j]=='D'){
                end = {i,j};
            }
        }
    }
    auto valid = [&](int y,int x) -> bool {
        return (y>=0 && y<n && x>=0 && x<n && grid[y][x]!='T');
    };
    while(!q1.empty()){
        int cy = q1.front().first, cx = q1.front().second;
        q1.pop();
        for(auto d: dirs){
            int ny = cy+d.first, nx = cx+d.second;
            if(!valid(ny,nx) || bear_dist[ny][nx]!=INF) continue;
            bear_dist[ny][nx] = bear_dist[cy][cx] + 1;
            q1.push({ny,nx});
        }
    }
    while(!q2.empty()){
        int cy = q2.front().first, cx = q2.front().second;
        q2.pop();
        for(auto d: dirs){
            int ny = cy+d.first, nx = cx+d.second;
            if(!valid(ny,nx) || bee_dist[ny][nx]!=INF || grid[ny][nx]=='D') continue;
            bee_dist[ny][nx] = bee_dist[cy][cx] + 1;
            q2.push({ny,nx});
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(bear_dist[i][j]==INF) continue;
            bear_dist[i][j] = ceil(bear_dist[i][j] / (double)s);
        }
    }
    function<void(int,int,int)> repl = [&](int y,int x,int cr){
        if(cr > s || !valid(y,x)) return;
        if(vis_dfs[y][x]) return;
        vis_dfs[y][x] = true;
        bear_dist[y][x] = 0;
        for(auto d: dirs){
            int ny = y+d.first, nx = x+d.second;
            repl(ny,nx,cr+1);
        }
    };
    repl(end.first,end.second,0);
    auto possible = [&](int w) -> bool {
        int sy = bear_start.first, sx = bear_start.second;
        if(bear_dist[sy][sx] + w >= bee_dist[sy][sx]) return false;
        vector<vector<bool>> vis(n, vector<bool>(n, false));
        queue<pair<int,int>> q;
        q.push({sy,sx});
        vis[sy][sx] = true;
        while(!q.empty()){
            int cy = q.front().first, cx = q.front().second;
            q.pop();
            if(grid[cy][cx]=='D') return true;
            for(auto d: dirs){
                int ny = cy+d.first, nx = cx+d.second;
                if(valid(ny,nx) && !vis[ny][nx] && bear_dist[ny][nx] + w < bee_dist[ny][nx]){
                    vis[ny][nx] = true;
                    q.push({ny,nx});
                }
            }
        }
        return false;
    };
    int lo = 0, hi = 1000000, ans = -1;
    while(lo <= hi){
        int mid = lo + (hi - lo) / 2;
        if(possible(mid)){
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 13 / 100