Submission #1215065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215065		daniutaiyang	Mecho (IOI09_mecho)	C++20	4 / 100	224 ms	131072 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
int n,speed,bees_dist[805][805],bear_dist[805][805];
char grid[805][805];
bool seen_bees[805][805],seen_bear[805][805];
pair<int,int> start,home,dirs[4] = {make_pair(0,1),make_pair(0,-1),make_pair(1,0),make_pair(-1,0)};
vector<pair<int,int> > hives;
deque<pair<int,int> > a;
void thing(){
    for(int i=0; i<805; i++){
        for(int j=0; j<805; j++){
            bear_dist[i][j] = 0;
            seen_bear[i][j] = false;
        }
    }
}
void thing2(int x){
    deque<pair<int,int> > b;
    b.push_back(start);
    seen_bear[start.first][start.second] = true;
    while(!b.empty()){
        pair<int,int> node = b.front();
        b.pop_front();
        for(auto d : dirs){
            int newx = newx, newy = newy;
            if(0<=newx&&newx<n&&0<=newy&&newy<n){
                if((grid[newx][newy]=='G'&&!seen_bear[newx][newy]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[newx][newy])||grid[newx][newy]=='D'){
                    seen_bear[newx][newy] = true;
                    bear_dist[newx][newy] = bear_dist[node.first][node.second]+1;
                    b.push_back(make_pair(newx,newy));
                }
            }
        }
    }
}
bool poss(int x){
    thing();
    thing2(x);
    if(seen_bear[home.first][home.second]&&bear_dist[home.first][home.second]!=0) return true;
    else return false;
}
int main(){
    cin >> n >> speed;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> grid[i][j];
            if(grid[i][j]=='H') hives.push_back(make_pair(i,j));
            else if(grid[i][j]=='M') start = make_pair(i,j);
            else if(grid[i][j]=='D') home = make_pair(i,j);
        }
    }
    for(auto hive : hives){
        a.push_back(hive);
        seen_bees[hive.first][hive.second] = true;
    }
    while(!a.empty()){
        pair<int,int> node = a.front();
        a.pop_front();
        for(auto d : dirs){
            int newx = newx, newy = newy;
            if(0<=newx&&newx<n&&0<=newy&&newy<n){
                if((grid[newx][newy]=='G'||grid[newx][newy]=='M')&&!seen_bees[newx][newy]){
                    seen_bees[newx][newy] = true;
                    bees_dist[newx][newy] = bees_dist[node.first][node.second]+1;
                    a.push_back(make_pair(newx,newy));
                }
            }
        }
    }
    if(!poss(0)){
        cout << "-1\n";
        return 0;
    }
    int low = 0, high = 1000000,ans=0;
    while(low<=high){
        int mid = (low+high)/2;
        if(poss(mid)){
            ans = mid;
            low = mid+1;
        }else high = mid-1;
    }
    cout << ans << '\n';
}

• Subtask 1: 4 / 100