Submission #1185269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185269		prism7k	Mecho (IOI09_mecho)	C++20	13 / 100	1096 ms	8920 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
 
const int INF = 2000000005;
char grid[800][800];
int bee_dist[800][800];
 
vector<pair<int,int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
 
bool valid(int y, int x, int n) {
    return y >= 0 && y < n && x >= 0 && x < n && grid[y][x] != 'T';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, s; 
    cin >> n >> s;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> grid[i][j];
        }
    }
    
    pair<int,int> bear_start, dest;
    vector<pair<int,int>> hives;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(grid[i][j]=='M') bear_start = {i,j};
            if(grid[i][j]=='D') dest = {i,j};
            if(grid[i][j]=='H') hives.push_back({i,j});
        }
    }
    
    // Compute bees' arrival times (in minutes) using a simple BFS.
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            bee_dist[i][j] = INF;
        }
    }
    queue<pair<int,int>> qb;
    for(auto &h : hives){
        int y = h.first, x = h.second;
        bee_dist[y][x] = 0;
        qb.push({y,x});
    }
    while(!qb.empty()){
        auto [y, x] = qb.front();
        qb.pop();
        for(auto d : dirs){
            int ny = y + d.first, nx = x + d.second;
            if(!valid(ny,nx,n)) continue;
            // Bees do not enter Mecho's home.
            if(grid[ny][nx]=='D') continue;
            if(bee_dist[ny][nx] > bee_dist[y][x] + 1){
                bee_dist[ny][nx] = bee_dist[y][x] + 1;
                qb.push({ny,nx});
            }
        }
    }
    
    // Compute minimal minutes required for Mecho to reach home from every cell.
    // In one minute, Mecho can make up to s steps. We perform a multi-minute BFS
    // from Mecho's home (destination) over the grid.
    vector<vector<int>> escape(n, vector<int>(n, INF));
    queue<pair<int,int>> mq;
    escape[dest.first][dest.second] = 0;
    mq.push(dest);
    while(!mq.empty()){
        auto [cy, cx] = mq.front();
        mq.pop();
        int nextTime = escape[cy][cx] + 1;
        vector<vector<bool>> used(n, vector<bool>(n, false));
        queue<tuple<int,int,int>> subq;  // (y, x, steps taken in current minute)
        subq.push({cy, cx, 0});
        used[cy][cx] = true;
        while(!subq.empty()){
            auto [y, x, steps] = subq.front();
            subq.pop();
            if(steps == s) continue;
            for(auto d : dirs){
                int ny = y + d.first, nx = x + d.second;
                if(!valid(ny, nx, n)) continue;
                if(!used[ny][nx]){
                    used[ny][nx] = true;
                    if(escape[ny][nx] > nextTime){
                        escape[ny][nx] = nextTime;
                        mq.push({ny,nx});
                    }
                    subq.push({ny, nx, steps + 1});
                }
            }
        }
    }
    
    // The "possible" function: can Mecho, by waiting w minutes before leaving,
    // follow a safe path from his start to home? At any cell (except home) he must
    // arrive strictly before the bees.
    auto possible = [&](int w) -> bool {
        // At the start cell, if waiting plus minimal required time from here is not less
        // than the bees' arrival time, then it's impossible.
        if(w + escape[bear_start.first][bear_start.second] >= bee_dist[bear_start.first][bear_start.second])
            return false;
        
        vector<vector<bool>> vis(n, vector<bool>(n, false));
        queue<pair<int,int>> qu;
        qu.push(bear_start);
        vis[bear_start.first][bear_start.second] = true;
        while(!qu.empty()){
            auto [y, x] = qu.front();
            qu.pop();
            if(grid[y][x]=='D')
                return true;
            for(auto d : dirs){
                int ny = y + d.first, nx = x + d.second;
                if(!valid(ny, nx, n)) continue;
                if(vis[ny][nx]) continue;
                // For cell (ny, nx), if the total time (waiting w plus the minimal minutes 
                // needed from there) is strictly less than the time bees arrive, then we
                // consider it safe.
                if(w + escape[ny][nx] < bee_dist[ny][nx]){
                    vis[ny][nx] = true;
                    qu.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