Submission #538243

#	Time	Username	Problem	Language	Result	Execution time	Memory
538243		erto	Mecho (IOI09_mecho)	C++17	100 / 100	630 ms	6096 KiB

mecho

#include <bits/stdc++.h>
typedef long long int ll;
#define INF (1e9 + 7)
#define INF2 (998244353)
#define N (ll)5e4+5
using namespace std;

int n, s, mx, my, dx, dy;
bool bb=0;
char a[802][802];
int d[802][802], d2[802][802];
vector<pair<int, int>> v;
 
void bfs(pair<int, int> p){
    queue<pair<int ,int>> q;
    pair<int, int> p2;
    int t;
    q.push(p);
    while(!q.empty()){
        p2 = q.front();
        q.pop();
        if(p2.first == dx && p2.second == dy)continue;
        t = d[p2.first][p2.second];
        if(p2.first > 1 && d[p2.first - 1][p2.second] > t + 1 && a[p2.first - 1][p2.second]!='T'){
            q.push({p2.first-1, p2.second});
            d[p2.first - 1][p2.second] = t + 1;
        }
        if(p2.second > 1 && d[p2.first][p2.second - 1] > t + 1 && a[p2.first][p2.second - 1]!='T'){
            q.push({p2.first, p2.second - 1});
            d[p2.first][p2.second - 1] = t + 1;
        }
        if(p2.first < n && d[p2.first + 1][p2.second] > t + 1 && a[p2.first + 1][p2.second]!='T'){
            q.push({p2.first+1, p2.second});
            d[p2.first + 1][p2.second] = t + 1;
        }
        if(p2.second < n && d[p2.first][p2.second + 1] > t + 1 && a[p2.first][p2.second + 1]!='T'){
            q.push({p2.first, p2.second + 1});
            d[p2.first][p2.second + 1] = t + 1;
        }
    }
}

void bfs2(int mid){
    queue<pair<int ,int>> q;
    pair<int, int> p2;
    int t;
    q.push({mx, my});
    while(!q.empty()){
        p2 = q.front();
        q.pop();
        t = d2[p2.first][p2.second];
        if(p2.first == dx + 1 && p2.second == dy){
            bb = 1;
            return;
        }
        if(p2.first == dx - 1 && p2.second == dy){
            bb = 1;
            return;
        }
        if(p2.first == dx && p2.second == dy - 1){
            bb = 1;
            return;
        }
        if(p2.first == dx && p2.second == dy + 1){
            bb = 1;
            return;
        }
        if(p2.first > 1 && d2[p2.first - 1][p2.second] > t + 1 && a[p2.first - 1][p2.second]!='T' && (t + 1)/s + mid < d[p2.first - 1][p2.second]){
            q.push({p2.first-1, p2.second});
            d2[p2.first - 1][p2.second] = t + 1;
        }
        if(p2.second > 1 && d2[p2.first][p2.second - 1] > t + 1 && a[p2.first][p2.second - 1]!='T' && (t + 1)/s + mid < d[p2.first][p2.second - 1]){
            q.push({p2.first, p2.second - 1});
            d2[p2.first][p2.second - 1] = t + 1;
        }
        if(p2.first < n && d2[p2.first + 1][p2.second] > t + 1 && a[p2.first + 1][p2.second]!='T' && (t + 1)/s + mid < d[p2.first + 1][p2.second]){
            q.push({p2.first+1, p2.second});
            d2[p2.first + 1][p2.second] = t + 1;
        }
        if(p2.second < n && d2[p2.first][p2.second + 1] > t + 1 && a[p2.first][p2.second + 1]!='T' && (t + 1)/s + mid < d[p2.first][p2.second + 1]){
            q.push({p2.first, p2.second + 1});
            d2[p2.first][p2.second + 1] = t + 1;
        }

    }
}

void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            d[i][j] =  INF;
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
            if(a[i][j] == 'H'){
                v.push_back({i, j});
                d[i][j] = 0;
            }
            if(a[i][j] == 'M'){
                mx = i;
                my = j;
            }
            if(a[i][j] == 'D'){
                dx = i;
                dy = j;
            }
        }
    }
    for(auto u : v){
        bfs(u);
    }
    d2[mx][my] = 0;

    int l=0, r=d[mx][my]-1, mid, ans=-1;
    while(r >= l){
        mid = (r+l)/2;
        bb = 0;
        memset(d2, INF, sizeof(d2));
        d2[mx][my] = 0;
        bfs2(mid);
        if(bb){
            ans = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    cout<<ans;
}   

int main(){ 
    //freopen("gravity.in", "r", stdin);
    //freopen("gravity.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

• Subtask 1: 100 / 100