Submission #1275113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275113		socialfox123	Mecho (IOI09_mecho)	C++20	97 / 100	1095 ms	10492 KiB

mecho

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

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];

    vector<vector<int>> beeDist(N, vector<int>(N, INF));
    queue<pii> q;
    pii start = {-1,-1}, home = {-1,-1};
    for(int r=0;r<N;r++){
        for(int c=0;c<N;c++){
            if(a[r][c]=='H'){
                beeDist[r][c] = 0;
                q.push({r,c});
            } else if(a[r][c]=='M') start = {r,c};
            else if(a[r][c]=='D') home = {r,c};
        }
    }

    // BFS for bees: they can move into any cell that is NOT 'T' and NOT 'D'
    while(!q.empty()){
        auto [r,c] = q.front(); q.pop();
        int d = beeDist[r][c];
        for(int k=0;k<4;k++){
            int nr=r+dr[k], nc=c+dc[k];
            if(nr<0||nr>=N||nc<0||nc>=N) continue;
            if(a[nr][nc]=='T' || a[nr][nc]=='D') continue; // bees can't go through trees or into D
            if(beeDist[nr][nc] > d+1){
                beeDist[nr][nc] = d+1;
                q.push({nr,nc});
            }
        }
    }
    // make D effectively safe: set beeDist[D] = INF (already INF because we didn't allow bees into D),
    // but ensure it explicitly:
    beeDist[home.first][home.second] = INF;

    // Helper: check if wait = w is possible
    auto can = [&](int w)->bool{
        // must be safe at start cell at time w
        if(beeDist[start.first][start.second] <= w) return false;

        // visited_global: cells we've already used as start-of-minute in previous iterations (avoid re-visiting forever)
        vector<vector<char>> used(N, vector<char>(N, 0));
        queue<pii> frontier; // cells that are start-of-minute at current time t
        used[start.first][start.second] = 1;
        frontier.push(start);
        int t = w; // current minute index (we start moving at minute t = w)

        // If start is itself D (unlikely by problem statement), success
        if(start == home) return true;

        while(!frontier.empty()){
            // BFS limited to depth S from all frontier sources, allowed to step only through cells with beeDist > t
            vector<pii> nextFront; // will be start-of-minute for t+1 (only cells with beeDist > t+1)
            queue<pair<pii,int>> qq;
            vector<vector<char>> seen(N, vector<char>(N,0)); // seen within this minute's multi-source S-BFS

            // push all frontier sources as depth 0
            int fsz = frontier.size();
            while(fsz--){
                auto p = frontier.front(); frontier.pop();
                qq.push({p,0});
                seen[p.first][p.second] = 1;
            }

            while(!qq.empty()){
                auto cur = qq.front(); qq.pop();
                int r = cur.first.first, c = cur.first.second, depth = cur.second;
                // If we reach home at any time, success
                if(r==home.first && c==home.second) return true;

                if(depth == S) continue; // can't go deeper this minute

                for(int k=0;k<4;k++){
                    int nr=r+dr[k], nc=c+dc[k];
                    if(nr<0||nr>=N||nc<0||nc>=N) continue;
                    if(seen[nr][nc]) continue;
                    // Mecho cannot go on trees or on H (hive). He can go on G, M, D.
                    if(a[nr][nc]=='T' || a[nr][nc]=='H') continue;
                    // He cannot step into a cell that has already been occupied by bees at start of minute t:
                    if(beeDist[nr][nc] <= t) continue;
                    seen[nr][nc] = 1;
                    qq.push({{nr,nc}, depth+1});
                }
            }

            // from seen (cells reached within <=S steps this minute), construct nextFront of cells that survive to next minute
            for(int r=0;r<N;r++){
                for(int c=0;c<N;c++){
                    if(!seen[r][c]) continue;
                    // If any reached cell is home we would have returned earlier.
                    if(r==home.first && c==home.second) return true;
                    // to survive to next minute (i.e., at start of minute t+1) Mecho's cell must have beeDist > t+1
                    if(beeDist[r][c] > t+1){
                        if(!used[r][c]){
                            used[r][c] = 1;
                            nextFront.push_back({r,c});
                        }
                    }
                }
            }

            // push nextFront into frontier queue
            for(auto &p: nextFront) frontier.push(p);
            // increment minute
            t++;
        }

        return false;
    };

    // Binary search maximum w
    int lo = 0, hi = N*N + 5; // hi is exclusive upper bound; safe big
    int ans = -1;
    while(lo <= hi){
        int mid = lo + (hi-lo)/2;
        if(can(mid)){
            ans = mid;
            lo = mid+1;
        } else hi = mid-1;
    }
    if(ans < 0) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}

• Subtask 1: 97 / 100