Submission #1198003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198003		daniutaiyang	Mecho (IOI09_mecho)	C++20	68 / 100	121 ms	12872 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,speed,bees_dist[805][805],bear_dist[805][805];
char grid[805][805];
bool seen_bees[805][805],seen_bear[805][805];
pair<ll,ll> start,home;
vector<pair<ll,ll> > hives;
deque<pair<ll,ll> > a;
void thing(){
    for(ll i=0; i<805; i++){
        for(ll j=0; j<805; j++){
            bear_dist[i][j] = 0;
            seen_bear[i][j] = false;
        }
    }
}
void thing2(ll x){
    deque<pair<ll,ll> > b;
    b.push_back(start);
    seen_bear[start.first][start.second] = true;
    while(!b.empty()){
        pair<ll,ll> node = b.front();
        b.pop_front();
        if(node.first!=0){
            if((grid[node.first-1][node.second]=='G'&&!seen_bear[node.first-1][node.second]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first-1][node.second])||grid[node.first-1][node.second]=='D'){
                seen_bear[node.first-1][node.second] = true;
                bear_dist[node.first-1][node.second] = bear_dist[node.first][node.second]+1;
                b.push_back(make_pair(node.first-1,node.second));
            }
        }
        if(node.second!=0){
            if((grid[node.first][node.second-1]=='G'&&!seen_bear[node.first][node.second-1]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first][node.second-1])||grid[node.first][node.second-1]=='D'){
                seen_bear[node.first][node.second-1] = true;
                bear_dist[node.first][node.second-1] = bear_dist[node.first][node.second]+1;
                b.push_back(make_pair(node.first,node.second-1));
            }
        }
        if(node.first!=n-1){
            if((grid[node.first+1][node.second]=='G'&&!seen_bear[node.first+1][node.second]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first+1][node.second])||grid[node.first+1][node.second]=='D'){
                seen_bear[node.first+1][node.second] = true;
                bear_dist[node.first+1][node.second] = bear_dist[node.first][node.second]+1;
                b.push_back(make_pair(node.first+1,node.second));
            }
        }
        if(node.second!=n-1){
            if((grid[node.first][node.second+1]=='G'&&!seen_bear[node.first][node.second+1]&&(bear_dist[node.first][node.second]+1)/speed+x<bees_dist[node.first][node.second+1])||grid[node.first][node.second+1]=='D'){
                seen_bear[node.first][node.second+1] = true;
                bear_dist[node.first][node.second+1] = bear_dist[node.first][node.second]+1;
                b.push_back(make_pair(node.first,node.second+1));
            }
        }
    }
}
bool poss(ll 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(ll i=0; i<n; i++){
        for(ll 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<ll,ll> node = a.front();
        a.pop_front();
        if(node.first!=0){
            if(grid[node.first-1][node.second]=='G'&&!seen_bees[node.first-1][node.second]){
                seen_bees[node.first-1][node.second] = true;
                bees_dist[node.first-1][node.second] = bees_dist[node.first][node.second]+1;
                a.push_back(make_pair(node.first-1,node.second));
            }
        }
        if(node.second!=0){
            if(grid[node.first][node.second-1]=='G'&&!seen_bees[node.first][node.second-1]){
                seen_bees[node.first][node.second-1] = true;
                bees_dist[node.first][node.second-1] = bees_dist[node.first][node.second]+1;
                a.push_back(make_pair(node.first,node.second-1));
            }
        }
        if(node.first!=n-1){
            if(grid[node.first+1][node.second]=='G'&&!seen_bees[node.first+1][node.second]){
                seen_bees[node.first+1][node.second] = true;
                bees_dist[node.first+1][node.second] = bees_dist[node.first][node.second]+1;
                a.push_back(make_pair(node.first+1,node.second));
            }
        }
        if(node.second!=n-1){
            if(grid[node.first][node.second+1]=='G'&&!seen_bees[node.first][node.second+1]){
                seen_bees[node.first][node.second+1] = true;
                bees_dist[node.first][node.second+1] = bees_dist[node.first][node.second]+1;
                a.push_back(make_pair(node.first,node.second+1));
            }
        }
    }
    ll low = 0, high = 1000000,ans=0;
    while(low<=high){
        ll mid = (low+high)/2;
        if(poss(mid)){
            ans = mid;
            low = mid+1;
        }else high = mid-1;
    }
    cout << ans << '\n';
}

• Subtask 1: 68 / 100