Submission #1039430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039430		ThommyDB	Mecho (IOI09_mecho)	C++17	11 / 100	103 ms	7028 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];

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> x = bear.front();
        bear.pop();
        if(ceil((float)bear_dist[x.first][x.second]/(float)s) +eat >= bee_dist[x.first][x.second])continue;

        if(x.first < n-1 && mp[x.first+1][x.second]=='D')return true;
        if(x.first > 0 && mp[x.first-1][x.second]=='D')return true;
        if(x.second < n-1 && mp[x.first][x.second+1]=='D')return true;
        if(x.second > 0 && mp[x.first][x.second-1]=='D')return true;

        if(x.first < n-1 && (mp[x.first+1][x.second]!='T' || mp[x.first+1][x.second]!='H') && bear_dist[x.first+1][x.second]==-1){
            bear_dist[x.first+1][x.second]=bear_dist[x.first][x.second]+1;
            bear.push({x.first+1, x.second});
        }
        if(x.first > 0 && (mp[x.first-1][x.second]!='T' || mp[x.first-1][x.second]!='H') && bear_dist[x.first-1][x.second]==-1){
            bear_dist[x.first-1][x.second]=bear_dist[x.first][x.second]+1;
            bear.push({x.first-1, x.second});
        }
        if(x.second < n-1 && (mp[x.first][x.second+1]!='T' || mp[x.first][x.second+1]!='H') && bear_dist[x.first][x.second+1]==-1){
            bear_dist[x.first][x.second+1]=bear_dist[x.first][x.second]+1;
            bear.push({x.first, x.second+1});
        }
        if(x.second > 0 && (mp[x.first][x.second-1]!='T' || mp[x.first][x.second-1]!='H') && bear_dist[x.first][x.second-1]==-1){
            bear_dist[x.first][x.second-1]=bear_dist[x.first][x.second]+1;
            bear.push({x.first, x.second-1});
        }
    }
    return false;
}

signed main(){
    cin >> n >> s;
    mp.resize(n, vector<char>(n));
    bee_dist.resize(n, vector<int>(n, INF));
    queue<pair<int, int>> bees;
    for(int i = 0; i < n; i++){
        for(int j = 0; 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> x = bees.front();
        bees.pop();
        if(x.first < n-1 && (mp[x.first+1][x.second]!='T' || mp[x.first+1][x.second]!='D' || mp[x.first+1][x.second]!='H') && bee_dist[x.first+1][x.second]==INF){
            bee_dist[x.first+1][x.second]=bee_dist[x.first][x.second]+1;
            bees.push({x.first+1, x.second});
        }
        if(x.first > 0 && (mp[x.first-1][x.second]!='T' || mp[x.first-1][x.second]!='D' || mp[x.first-1][x.second]!='H') && bee_dist[x.first-1][x.second]==INF){
            bee_dist[x.first-1][x.second]=bee_dist[x.first][x.second]+1;
            bees.push({x.first-1, x.second});
        }
        if(x.second < n-1 && (mp[x.first][x.second+1]!='T' || mp[x.first][x.second+1]!='D' || mp[x.first][x.second+1]!='H') && bee_dist[x.first][x.second+1]==INF){
            bee_dist[x.first][x.second+1]=bee_dist[x.first][x.second]+1;
            bees.push({x.first, x.second+1});
        }
        if(x.second > 0 && (mp[x.first][x.second-1]!='T' || mp[x.first][x.second-1]!='D' || mp[x.first][x.second-1]!='H') && bee_dist[x.first][x.second-1]==INF){
            bee_dist[x.first][x.second-1]=bee_dist[x.first][x.second]+1;
            bees.push({x.first, x.second-1});
        }
    }

    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: 11 / 100