Submission #1275095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275095		lmduc270410	Mecho (IOI09_mecho)	C++20	46 / 100	1097 ms	19004 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int MAXN = 805;
const int INF = 1e9;

int n, k;
string a[MAXN];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int bees_time[MAXN][MAXN];

// flattened helpers
inline int id(int x, int y){ return x * n + y; }
inline int xi(int idd){ return idd / n; }
inline int yi(int idd){ return idd % n; }

// compute bees_time once
void compute_bees_time(){
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) bees_time[i][j] = INF;
    queue<pii> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j] == 'H'){
                bees_time[i][j] = 0;
                q.push({i,j});
            }
        }
    }
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        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 spread into G or M (treat M like G)
            if(!(a[nx][ny]=='G' || a[nx][ny]=='M')) continue;
            if(bees_time[nx][ny] == INF){
                bees_time[nx][ny] = bees_time[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    // bees_time at D remains INF
}

// Global visit tokens to avoid clearing arrays
static int seen_mark[MAXN*MAXN];
static int inbfs_mark[MAXN*MAXN];
static int seen_token = 1;
static int inbfs_token = 1;

// can(t): Me waits t minutes, can he reach D?
bool can(int t){
    int sx=-1, sy=-1, tx=-1, ty=-1;
    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(sx==-1 || tx==-1) return false;
    if(bees_time[sx][sy] <= t) return false;

    // curr = flattened positions Me can stand at start of a minute
    vector<int> curr;
    curr.reserve(n*n);
    curr.push_back(id(sx,sy));
    ++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; } // avoid zero wrap
    ++inbfs_token;

    int time = t;
    while(!curr.empty()){
        // BFS multi-source limited to depth k
        // We'll use arrays as circular queue to store nodes and depth
        int qsize = n * n + 5;
        static int qnodes[MAXN*MAXN];
        static int qdepth[MAXN*MAXN];
        int qhead = 0, qtail = 0;

        ++inbfs_token;
        if(inbfs_token==0){ ++inbfs_token; ++seen_token; } // safety for wrap

        // push all current starts
        for(int pos : curr){
            int x = xi(pos), y = yi(pos);
            if(bees_time[x][y] <= time) continue; // unsafe at start of minute
            // immediate success if at D
            if(x==tx && y==ty) return true;
            if(inbfs_mark[pos] != inbfs_token){
                inbfs_mark[pos] = inbfs_token;
                qnodes[qtail] = pos;
                qdepth[qtail] = 0;
                ++qtail;
            }
        }

        vector<int> next; next.reserve(n*n/4);

        // BFS limited
        while(qhead < qtail){
            int curpos = qnodes[qhead];
            int d = qdepth[qhead];
            ++qhead;
            int x = xi(curpos), y = yi(curpos);
            if(x==tx && y==ty) return true;
            // can stand here at end of minute if bees arrive later than time+1
            if(bees_time[x][y] > time + 1 && seen_mark[curpos] != seen_token){
                seen_mark[curpos] = seen_token;
                next.push_back(curpos);
            }
            if(d == k) continue;
            // expand neighbors
            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;
                char ch = a[nx][ny];
                if(!(ch=='G' || ch=='D' || ch=='M')) continue;
                if(bees_time[nx][ny] <= time) continue; // cannot step into bees-occupied at start
                int nid = id(nx,ny);
                if(inbfs_mark[nid] == inbfs_token) continue;
                inbfs_mark[nid] = inbfs_token;
                qnodes[qtail] = nid;
                qdepth[qtail] = d+1;
                ++qtail;
            }
        }

        // advance minute
        time++;
        ++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; }

        curr.swap(next);
    }
    return false;
}

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

    compute_bees_time();

    int l=0, r = n * n, 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: 46 / 100