Submission #1286642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286642		opeleklanos	Mecho (IOI09_mecho)	C++20	36 / 100	1097 ms	51308 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] != 'G' && grid[y][x] != 'H') return 0;
    minReachBees[y][x] = tm;
    return 1;
}

void upd(ll y, ll x){
    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});

    while(!q.empty()){
        auto tmp = q.front();
        q.pop();
        upd(tmp.first, tmp.second);
    }
}

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/s >= minReachBees[y][x]) return 0;
    mr[y][x] = tm;
    return 1;
}

void check(ll y, ll x){
    vis[x][y] = 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});

    while(!q.empty()){
        auto tmp = q.front();
        q.pop();
        check(tmp.first, tmp.second);
    }
}


int main(void){
  //  freopen("input.txt", "r", stdin);
    cin>>n>>s;
    grid.assign(n, vector<char>(n, 0));
    minReachBees.assign(n, vector<ll>(n, 100000000));
    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;
                upd(i, j);
            }
            if(grid[i][j] == 'M'){
                m = {i, j};
            }
            if(grid[i][j] == 'D'){
                h = {i, j};
            }
        }
    }

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

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

• Subtask 1: 36 / 100