Submission #1040188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040188		ThommyDB	Mecho (IOI09_mecho)	C++17	100 / 100	125 ms	7060 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n, s;
vector<vector<char>> mp;
pair<int, int> m;
vector<vector<int>> bee_dist;
int bear_dist[805][805];
vector<pair<int, int>> allowed_moves{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool check(int eat){
    queue<pair<int, int>> bear;
    memset(bear_dist, -1, sizeof(bear_dist));
    bear_dist[m.first][m.second] = 0;
    bear.push(m);
    while(!bear.empty()){
        pair<int, int> pos = bear.front();
        bear.pop();
        if(bear_dist[pos.first][pos.second]/s + eat >= bee_dist[pos.first][pos.second])continue;

        for(pair<int, int> u : allowed_moves){
            int x = pos.first + u.first, y = pos.second + u.second;
            if(x > 0 && x < n+1 && y > 0 && y < n+1 && mp[x][y]=='D')return true;
            if(bear_dist[x][y]==-1 && x > 0 && x < n+1 && y > 0 && y < n+1 && mp[x][y] != 'D' && mp[x][y] != 'T'){
                bear_dist[x][y]=bear_dist[pos.first][pos.second] + 1;
                bear.push({x, y});
            }
        }
    }
    return false;
}

signed main(){
    cin >> n >> s;
    mp.resize(n+2, vector<char>(n+2));
    bee_dist.resize(n+2, vector<int>(n+2, INF));
    queue<pair<int, int>> bees;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> mp[i][j];
            if(mp[i][j]=='M')m={i, j};
            else if(mp[i][j]=='H'){
                bees.push({i, j});
                bee_dist[i][j]=0;
            }
        }  
    }

    while(!bees.empty()){
        pair<int, int> pos = bees.front();
        bees.pop();
        for(pair<int, int> u : allowed_moves){
            int x = pos.first+u.first, y = pos.second+u.second;
            if(bee_dist[x][y]==INF && x > 0 && x < n+1 && y > 0 && y < n+1 && mp[x][y]!= 'D' && mp[x][y] != 'T'){
                bee_dist[x][y] = bee_dist[pos.first][pos.second]+1;
                bees.push({x, y});
            }
        }
    }

    int l = -1, r = n*n;
    while(l<r){
        int mid = (l+r+1)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout << l << "\n";
}

• Subtask 1: 100 / 100