제출 #443367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443367		MohammadAghil	Mecho (IOI09_mecho)	C++14	95 / 100	260 ms	11540 KiB

mecho

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 
 
const ll mod = 998244353, maxn = 800 + 5, inf = 1e18 + 5;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool bad[maxn][maxn];
ll dist_bee[maxn][maxn], dist[maxn][maxn];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, s; cin >> n >> s;
    pair<ll, ll> st, en;
    deque<pair<ll, ll>> hol;  
    rep(i,0,n){
        rep(j,0,n){
            dist_bee[i][j] = inf;
            char e; cin >> e;
            if(e == 'M'){
                st = {i, j};
            }
            if(e == 'D'){
                en = {i, j};
            }
            if(e == 'H'){
                hol.push_back({i, j});
                dist_bee[i][j] = 0;
            }
            if(e == 'H' || e == 'T') bad[i][j] = 1;
        }
    }
    while(sz(hol)){
        pair<ll, ll> p = hol.front(); hol.pop_front();
        rep(d,0,4){
            ll i = p.ff + dx[d], j = p.ss + dy[d];
            if(i < 0 || i >= n || j < 0 || j >= n || dist_bee[i][j] != inf || bad[i][j]) continue;
            dist_bee[i][j] = dist_bee[p.ff][p.ss] + s;
            hol.pb({i, j});
        }
    }

    dist_bee[en.ff][en.ss] = inf;
    auto chk = [&](ll t) -> bool{
        if(dist_bee[st.ff][st.ss] <= 1LL*t*s) return 0; 
        rep(i,0,n){
            rep(j,0,n){
                dist[i][j] = inf;
            }
        }
        dist[st.ff][st.ss] = 1LL*t*s;
        deque<pair<ll, ll>> q;
        q.push_back(st);
        while(sz(q)){
            pair<ll, ll> p = q.front(); q.pop_front();
            rep(d,0,4){
                ll i = p.ff + dx[d], j = p.ss + dy[d];
                if(i < 0 || i >= n || j < 0 || j >= n || bad[i][j] 
                    || dist[i][j] != inf || (dist[p.ff][p.ss] + 1) >= dist_bee[i][j]) continue;
                dist[i][j] = dist[p.ff][p.ss] + 1;
                q.push_back({i, j});
            }
        }
        return dist[en.ff][en.ss] != inf;
    };
    ll l = -1, r = 1e7;
    while(l + 1 < r){
        ll mid = (l + r)/2;
        if(chk(mid)) l = mid;
        else r = mid;
    }
    cout << l;
    return 0;
}

• Subtask 1: 95 / 100