제출 #1287065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287065		opeleklanos	Mecho (IOI09_mecho)	C++20	100 / 100	662 ms	11292 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define ll long long

vector<vector<char>> grid;
vector<vector<ll>> minReachBees;
vector<vector<ll>> mr;
vector<vector<bool>> vis;

queue<pair<ll, ll>> q;

ll n, s;

ll isOk1(ll y, ll x, ll tm){
    if(y>=n||x>=n||y<0||x<0) return 0;
    if(minReachBees[y][x] <= tm) return 0 ;
    if(grid[y][x] == 'T' || grid[y][x] == 'D') return 0;
    minReachBees[y][x] = tm;
    return 1;
}

void upd(){
    while(!q.empty()){
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        ll tm = minReachBees[y][x];
        if(isOk1(y+1, x, tm+1)) q.push({y+1, x});
        if(isOk1(y-1, x, tm+1)) q.push({y-1, x});
        if(isOk1(y, x+1, tm+1)) q.push({y, x+1});
        if(isOk1(y, x-1, tm+1)) q.push({y, x-1});
    }
}

ll isOk2(ll y, ll x, ll tm){
    if(y>=n||x>=n||y<0||x<0) return 0;
    if(mr[y][x] <= tm) return 0 ;
    if(grid[y][x] == 'T') return 0;
    if(vis[y][x] == 1) return 0;
    if(tm >= minReachBees[y][x]*s) return 0;
    mr[y][x] = tm;
    return 1;
}

void check(){
    while(!q.empty()){
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        vis[y][x] = 1;
        ll tm = mr[y][x];
        if(isOk2(y+1, x, tm+1)) q.push({y+1, x});
        if(isOk2(y-1, x, tm+1)) q.push({y-1, x});
        if(isOk2(y, x+1, tm+1)) q.push({y, x+1});
        if(isOk2(y, x-1, tm+1)) q.push({y, x-1});
    }
}


int main(void){
   // freopen("input.txt", "r", stdin);
    cin>>n>>s;
    grid.assign(n, vector<char>(n, 0));
    minReachBees.assign(n, vector<ll>(n, 100000000000));
    for(ll i = 0; i<n; i++){
        string str; cin>>str;
        for(ll j = 0; j<n; j++){
            grid[i][j] = str[j];
        }
    }

    pair<ll, ll> m;
    pair<ll, ll> h;
    for(ll i = 0; i<n; i++){
        for(ll j = 0; j<n; j++){
            if(grid[i][j] == 'H'){
                minReachBees[i][j] = 0;
                q.push({i, j});
                upd();
            }
            if(grid[i][j] == 'M'){
                m = {i, j};
            }
            if(grid[i][j] == 'D'){
                h = {i, j};
            }
        }
    }

    mr.assign(n, vector<ll>(n, 100000000000));
    vis.assign(n, vector<bool>(n, 0));
    mr[m.first][m.second] = 0;
    q.push({m.first, m.second});
    check();
    if(mr[h.first][h.second] == 100000000000){
        cout<<-1<<endl;
        return 0;
    }

    ll l = 0, r = 100000000000;
    while(l<r){
        ll mid = (l+r+1)/2;
        mr.assign(n, vector<ll>(n, 100000000000));
        vis.assign(n, vector<bool>(n, 0));
        mr[m.first][m.second] = mid*s;
        q.push({m.first, m.second});
        check();
        int cor = 0;
        if(minReachBees[m.first][m.second] <= mid){
            r = mid-1;
            //continue;
        }
        // if(h.first<n-1 && mr[h.first+1][h.second] != 100000000000) cor = 1;
        // if(h.first>0 && mr[h.first-1][h.second] != 100000000000) cor = 1;
        // if(h.second>0 && mr[h.first][h.second-1] != 100000000000) cor = 1;
        // if(h.second<n-1 && mr[h.first][h.second+1] != 100000000000) cor = 1;
        else if(mr[h.first][h.second] != 100000000000 || cor) l = mid;
        else r = mid-1;
    }
    cout<<l<<endl;
    return 0;
}

• Subtask 1: 100 / 100