Submission #535726

#	Time	Username	Problem	Language	Result	Execution time	Memory
535726		louiskwok	Mecho (IOI09_mecho)	C++17	100 / 100	222 ms	6880 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
bool visited[805][805];
int distBee[805][805];
int distBear[805][805];
char g[805][805];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int n,s,sr,sc,er,ec,mxtime;
bool possible(int t) {
    memset(visited,0,sizeof visited);
    queue < pair <pair<int,int>,int> > bfs;
    bfs.push({{sr,sc},0});
    visited[sr][sc] = true;
    distBear[sr][sc] = t;
    if (distBear[sr][sc]>=distBee[sr][sc]) return false;
    while (!bfs.empty()) {
        int curR = bfs.front().first.first;
        int curC = bfs.front().first.second;
        int steps = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||distBear[curR][curC]+((steps+1)%s==0?1:0)>=distBee[nr][nc]) continue;
            visited[nr][nc] = true;
            distBear[nr][nc] = distBear[curR][curC] + ((steps+1)%s==0?1:0);
            bfs.push({{nr,nc},steps+1});
        }
    }
    if (visited[er][ec]) return true;
    return false;
}
int main() {
    queue < pair<int,int> > bfs;
    cin >> n >> s;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            cin >> g[i][j];
            distBee[i][j]=1000000;
            if (g[i][j]=='M') sr = i,sc = j;
            else if (g[i][j]=='D') er = i,ec = j;
            else if (g[i][j]=='H') {
                visited[i][j] = true;
                distBee[i][j] = 0;
                bfs.push({i,j});
            }
        }
    }
    while (!bfs.empty()) {
        int curR = bfs.front().first;
        int curC = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||g[nr][nc]=='D') continue;
            visited[nr][nc] = true;
            distBee[nr][nc] = distBee[curR][curC]+1;
            mxtime = max(mxtime,distBee[nr][nc]);
            bfs.push({nr,nc});
        }
    }
    int lo = 0,hi = mxtime;
    while (lo<hi) {
        int mid = (lo+hi+1)/2;
        bool poss = possible(mid);
        if (poss) lo = mid;
        else hi = mid-1;
    }
    if (!possible(0)) cout << -1 << endl;
    else cout << lo << endl;
    return 0;
}

• Subtask 1: 100 / 100