Submission #1275098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275098		lmduc270410	Mecho (IOI09_mecho)	C++20	46 / 100	1097 ms	15440 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];
int sx=-1, sy=-1, tx=-1, ty=-1;

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

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});
            }
            if(a[i][j] == 'M'){ sx=i; sy=j; }
            if(a[i][j] == 'D'){ tx=i; ty=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;
            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[tx][ty] stays INF (bees don't enter D)
}

// --- token arrays to avoid memset ---
static int seen_mark[MAXN*MAXN];
static int inbfs_mark[MAXN*MAXN];
static int seen_token = 2;
static int inbfs_token = 4;

// static arrays to avoid allocations
static int curr_arr[MAXN*MAXN];
static int next_arr[MAXN*MAXN];
static int qnodes[MAXN*MAXN];
static int qdepth[MAXN*MAXN];

bool can(int t){
    if(sx==-1 || tx==-1) return false;
    if(bees_time[sx][sy] <= t) return false;

    int curr_sz = 0;
    curr_arr[curr_sz++] = id(sx, sy);
    ++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; }
    ++inbfs_token; if(inbfs_token==0){ ++inbfs_token; ++seen_token; }

    int time = t;
    while(curr_sz){
        // BFS multi-source limited to depth k
        int qhead = 0, qtail = 0;
        ++inbfs_token; if(inbfs_token==0){ ++inbfs_token; ++seen_token; }

        // push all current
        for(int i=0;i<curr_sz;i++){
            int pos = curr_arr[i];
            int x = xi(pos), y = yi(pos);
            if(bees_time[x][y] <= time) continue; // unsafe at start
            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;
            }
        }

        int next_sz = 0;

        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;
            if(bees_time[x][y] > time + 1 && seen_mark[curpos] != seen_token){
                seen_mark[curpos] = seen_token;
                next_arr[next_sz++] = curpos;
            }
            if(d == k) 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;
                char ch = a[nx][ny];
                if(!(ch=='G' || ch=='D' || ch=='M')) continue;
                if(bees_time[nx][ny] <= time) continue;
                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;
            }
        }

        time++;
        ++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; }
        // swap curr and next
        curr_sz = next_sz;
        for(int i=0;i<next_sz;i++) curr_arr[i] = next_arr[i];
    }
    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();

    // set upper bound r more tightly:
    int r;
    if(bees_time[sx][sy] == INF) r = n * n; // bees never reach M -> cap at n*n
    else r = min(n * n, bees_time[sx][sy] - 1); // cannot wait >= bees_time[sx][sy]
    int l = 0, 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