Submission #1215067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215067		daniutaiyang	Mecho (IOI09_mecho)	C++20	84 / 100	149 ms	7532 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){
            if(0<=node.first+d.first&&node.first+d.first<n&&0<=node.second+d.second&&node.second+d.second<n){
                if((grid[node.first+d.first][node.second+d.second]=='G'&&!seen_bear[node.first+d.first][node.second+d.second]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first+d.first][node.second+d.second])||grid[node.first+d.first][node.second+d.second]=='D'){
                    seen_bear[node.first+d.first][node.second+d.second] = true;
                    bear_dist[node.first+d.first][node.second+d.second] = bear_dist[node.first][node.second]+1;
                    b.push_back(make_pair(node.first+d.first,node.second+d.second));
                }
            }
        }
    }
}
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){
            if(0<=node.first+d.first&&node.first+d.first<n&&0<=node.second+d.second&&node.second+d.second<n){
                if((grid[node.first+d.first][node.second+d.second]=='G'||grid[node.first+d.first][node.second+d.second]=='M')&&!seen_bees[node.first+d.first][node.second+d.second]){
                    seen_bees[node.first+d.first][node.second+d.second] = true;
                    bees_dist[node.first+d.first][node.second+d.second] = bees_dist[node.first][node.second]+1;
                    a.push_back(make_pair(node.first+d.first,node.second+d.second));
                }
            }
        }
    }
    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;
    }
    if(!poss(ans)) cout << "-1\n";
    else cout << ans << '\n';
}

• Subtask 1: 84 / 100