Submission #1275091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275091		lmduc270410	Mecho (IOI09_mecho)	C++20	53 / 100	578 ms	7652 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 1e9;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, S;
    if(!(cin >> n >> S)) return 0;
    vector<string> a(n);
    for(int i=0;i<n;i++) cin >> a[i];

    int sx=-1, sy=-1, tx=-1, ty=-1;
    vector<pii> hives;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j] == 'M'){ sx=i; sy=j; }
            if(a[i][j] == 'D'){ tx=i; ty=j; }
            if(a[i][j] == 'H'){ hives.push_back({i,j}); }
        }
    }

    // bees_time: minute when bees first occupy cell (hive = 0). D is not enterable -> keep INF.
    vector<vector<int>> bees(n, vector<int>(n, INF));
    queue<pii> q;
    for(auto &h : hives){
        bees[h.first][h.second] = 0;
        q.push(h);
    }
    while(!q.empty()){
        auto [x,y] = q.front(); q.pop();
        for(int dir=0; dir<4; ++dir){
            int nx = x + dx[dir], ny = y + dy[dir];
            if(nx<0||nx>=n||ny<0||ny>=n) continue;
            // bees can spread only into grassy cells (G or M initially). not into T or D or H again.
            if(a[nx][ny] == 'G' || a[nx][ny] == 'M'){
                if(bees[nx][ny] == INF){
                    bees[nx][ny] = bees[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    // Note: bees[tx][ty] stays INF because bees cannot enter D.

    // check(t): can Mecho wait t minutes then still reach D?
    auto can = [&](int t)->bool{
        if(bees[sx][sy] <= t) return false; // bees already reach honey while Mecho still there
        vector<vector<char>> seen(n, vector<char>(n, 0));
        queue<pii> curr;
        curr.push({sx, sy});
        seen[sx][sy] = 1;
        int time = t; // bees have occupied all cells with bees[..] <= time
        while(!curr.empty()){
            // within this minute, Mecho can move up to S steps.
            // BFS-limited to depth S starting from all nodes in curr (multi-source).
            queue<pair<pii,int>> bfsq;
            vector<vector<char>> inbfs(n, vector<char>(n, 0));
            // push all current positions as starting nodes (depth 0)
            int sz = (int)curr.size();
            while(sz--){
                auto p = curr.front(); curr.pop();
                int x = p.first, y = p.second;
                // If Mecho at any time inside minute reaches home, succeed immediately.
                if(x == tx && y == ty) return true;
                // Note: we should allow starting positions only if not currently occupied by bees:
                if(bees[x][y] <= time) continue; // already unsafe at start of minute
                bfsq.push({{x,y}, 0});
                inbfs[x][y] = 1;
            }

            queue<pii> next; // positions Mecho can be at end of this minute
            while(!bfsq.empty()){
                auto cur = bfsq.front(); bfsq.pop();
                int x = cur.first.first, y = cur.first.second, d = cur.second;
                // If he steps onto D at any time -> safe immediately
                if(x == tx && y == ty) return true;
                // he can stand here at end of minute only if bees won't reach it at end of minute
                if(bees[x][y] > time + 1 && !seen[x][y]){
                    next.push({x,y});
                    seen[x][y] = 1;
                }
                if(d == S) continue;
                for(int dir=0; dir<4; ++dir){
                    int nx = x + dx[dir], ny = y + dy[dir];
                    if(nx<0||nx>=n||ny<0||ny>=n) continue;
                    if(inbfs[nx][ny]) continue;
                    // Mecho can travel on G or D (and M originally treated as G)
                    if(!(a[nx][ny] == 'G' || a[nx][ny] == 'D' || a[nx][ny] == 'M')) continue;
                    // cannot step into a cell that bees already occupy at start of this minute
                    if(bees[nx][ny] <= time) continue;
                    inbfs[nx][ny] = 1;
                    bfsq.push({{nx,ny}, d+1});
                }
            }

            // advance minute
            time++;
            // prepare for next minute
            curr = move(next);
        }
        return false;
    };

    // binary search maximum t (minutes) such that can(t) == true
    int l = 0, r = 2*n; // as argued, 2*n is safe upper bound in minutes
    int ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(can(mid)){
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 53 / 100