Submission #1138999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138999		abel2008	Mecho (IOI09_mecho)	C++20	100 / 100	131 ms	6308 KiB

mecho

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cassert>
using namespace std;
const int INF = 10000000;
int n,s;
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
char mat[805][805];
vector<pair<int,int>> hives;
int homei,homej;
int starti,startj;
int bee_dist[805][805],mecho_dist[805][805];

bool validbee(int x,int y) {
        if (!(x>=1&&x<=n&&y>=1&&y<=n))
                return false;
        if (mat[x][y]=='G'||mat[x][y]=='M')
                return true;
        return false;
}

bool validmecho(int x,int y) {
        if (!(x>=1&&x<=n&&y>=1&&y<=n))
                return false;
        if (mat[x][y]=='T'||mat[x][y]=='H')
                return false;
        return true;
}

bool beforebee(int x,int y,int dist,int offset) {
        if (dist/s+offset<bee_dist[x][y])
                return true;
        return false;
}

void reset() {
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=n;++j) {
                        mecho_dist[i][j] = INF;
                }
        }
}

bool reachable(int tiempo) {
        reset();
        queue<pair<int,int>> q;
        q.emplace(starti,startj);
        if (bee_dist[starti][startj] <= tiempo) { q.pop(); }
        mecho_dist[starti][startj] = 0;
        while(!q.empty()) {
                auto crt = q.front();
                q.pop();
                int x = crt.first,y = crt.second;
                for (int k = 0;k<4;++k) {
                        int crtx = x+dx[k],crty = y+dy[k];
                        if (validmecho(crtx,crty)&&crtx==homei&&crty==homej) {
                                return true;
                        }
                        if (validmecho(crtx,crty)&&mecho_dist[x][y]+1<mecho_dist[crtx][crty]&&beforebee(crtx,crty,mecho_dist[x][y]+1,tiempo)) {
                                q.emplace(crtx,crty);
                                mecho_dist[crtx][crty] = mecho_dist[x][y]+1;
                        }
                }
        }
        return false;
}

int main() {
        cin>>n>>s;
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=n;++j) {
                        bee_dist[i][j] = INF;
                        mecho_dist[i][j] = INF;
                        cin>>mat[i][j];
                        if (mat[i][j]=='H') {
                                hives.emplace_back(i,j);
                        } else if (mat[i][j]=='D') {
                                homei = i;
                                homej = j;
                        } else if (mat[i][j]=='M') {
                                starti = i;
                                startj = j;
                        }
                }
        }
        queue<pair<int,int>> q;
        for (const auto &[f,s] : hives) {
                q.emplace(f,s);
                bee_dist[f][s] = 0;
        }
        // bee bfs
        while(!q.empty()) {
                auto crt = q.front();
                q.pop();
                int x = crt.first,y = crt.second;
                for (int k = 0;k<4;++k) {
                        int crtx = x+dx[k],crty = y+dy[k];
                        if (validbee(crtx,crty)&&bee_dist[x][y]+1<bee_dist[crtx][crty]) {
                                bee_dist[crtx][crty] = bee_dist[x][y]+1;
                                q.emplace(crtx,crty);
                        }
                }
        }
        // queue should be empty
        assert(q.empty());
        // now lets bfs for mecho
        // l is always safe, r is never safe;
        // l<=x,r >x
        // find max good x
        int l = -1,r = 10000000;
        while(l+1!=r) {
                int mid = (l+r)/2;
                if (reachable(mid)) {
                        l = mid;
                } else {
                        r = mid;
                }
        }
        cout<<l;
        return 0;
}

• Subtask 1: 100 / 100