Submission #1200954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200954		apelpisia	Mecho (IOI09_mecho)	C++20	0 / 100	439 ms	131072 KiB

mecho

#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;

const int nx = 805;
int n, s, l=0, r=2000, md, ans=-1;
string grid[nx];
pair<int, int> bear, home, dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
set<pair<int, int>> bee;

bool check(int steps){
    vector<vector<bool>> bg(nx, vector<bool>(nx, false));
    queue<pair<int, pair<int, int>>> q, bq;
    for(auto [y, x] : bee) q.push({0, {y, x}});
    while(q.front().ff<md){
        int mins = q.front().ff;
        pair<int, int> pos = q.front().ss;
        q.pop();
        for(int i=0; i<4; i++){
            if(pos.ff+dir[i].ff>=0 && pos.ff+dir[i].ff<n && pos.ss+dir[i].ss>=0 && pos.ss+dir[i].ss<n){
                if(pos.ff+dir[i].ff==bear.ff && pos.ss+dir[i].ss==bear.ss) return false;
                else if(!bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss]){
                    q.push({mins+1, {pos.ff+dir[i].ff, pos.ss+dir[i].ss}});
                    bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss] = true;
                }
            }
        }
    }
    bq.push({0, {bear.ff, bear.ss}});
    int bcnt=md+1, brcnt=steps;
    while(!bq.empty()){
        while(bq.front().ff<brcnt){
            int mins = bq.front().ff;
            pair<int, int> pos = bq.front().ss;
            bq.pop();
            if(bg[pos.ff][pos.ss]) continue;
            for(int i=0; i<4; i++){
                if(pos.ff+dir[i].ff>=0 && pos.ff+dir[i].ff<n && pos.ss+dir[i].ss>=0 && pos.ss+dir[i].ss<n){
                    if(pos.ff+dir[i].ff==home.ff && pos.ss+dir[i].ss==home.ss) return true;
                    else if(!bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss]){
                        bq.push({mins+1, {pos.ff+dir[i].ff, pos.ss+dir[i].ss}});
                    }
                }
            }
        } brcnt+=steps;
        while(q.front().ff<bcnt){
            int mins = q.front().ff;
            pair<int, int> pos = q.front().ss;
            q.pop();
            for(int i=0; i<4; i++){
                if(pos.ff+dir[i].ff>=0 && pos.ff+dir[i].ff<n && pos.ss+dir[i].ss>=0 && pos.ss+dir[i].ss<n){
                    if(pos.ff+dir[i].ff==bear.ff && pos.ss+dir[i].ss==bear.ss) return false;
                    else if(!bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss]){
                        q.push({mins+1, {pos.ff+dir[i].ff, pos.ss+dir[i].ss}});
                        bg[pos.ff+dir[i].ff][pos.ss+dir[i].ss] = true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> grid[i];
        for(int j=0; j<n; j++){
            if(grid[i][j]=='H') bee.insert({i, j});
            else if(grid[i][j]=='M') bear = {i, j};
            else if(grid[i][j]=='D') home = {i, j};
        }
    }
    while(l<=r){
        md = l+(r-l)/2;
        if(check(s)){
            ans = md;
            l = md+1;
        } else r = md-1;
    }
    cout << ans-1;

    return 0;
}

• Subtask 1: 0 / 100