Submission #1306730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306730		vaishakhv	Mecho (IOI09_mecho)	C++20	29 / 100	185 ms	15108 KiB

mecho

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll cap = 1e3+1;
bool visited[cap][cap];
ll dist[cap][cap];
ll distmecho[cap][cap];
string grid[cap];
queue<pair<ll,ll>> q_multi;
queue<pair<ll,ll>> q;
ll n, s;
pair<ll,ll> m, d;

void multi_bfs(){
    while(!q_multi.empty()){
        pair<ll,ll> top = q_multi.front(); q_multi.pop();
        ll y = top.first, x = top.second;
        vector<pair<ll,ll>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (auto dir: dirs){
            ll dy = dir.first, dx = dir.second;
            if (y+dy < 0 || x+dx < 0 || y+dy >= n || x + dx >= n) continue;
            if (grid[y+dy][x+dx] == 'T' || grid[y+dy][x+dx] == 'D') continue;
            if (visited[y+dy][x+dx]) continue;
            visited[y+dy][x+dx] = true;
            dist[y+dy][x+dx] = dist[y][x] + 1;
            q_multi.push({y+dy,x+dx});
        }
    }
}

void bfs(ll mid){
    while(!q.empty()){
        pair<ll,ll> top = q.front(); q.pop();
        ll y = top.first, x = top.second;
        
        vector<pair<ll,ll>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (auto dir: dirs){
            ll dy = dir.first, dx = dir.second;
            if (y+dy < 0 || x + dx < 0 || y+dy >= n || x + dx >= n) continue;
            if (grid[y+dy][x+dx] == 'T' || grid[y+dy][x+dx] == 'H') continue;
            
            if (distmecho[y+dy][x+dx] != 1e18) continue;

            ll steps = distmecho[y][x] + 1;
            ll minutes = (steps + s - 1) / s;

            if (grid[y+dy][x+dx] == 'D') {
                if (mid + minutes < dist[y+dy][x+dx]) {
                    distmecho[y+dy][x+dx] = steps;
                    return;
                }
            }

            if (mid + minutes < dist[y+dy][x+dx]) {
                distmecho[y+dy][x+dx] = steps;
                q.push({y+dy, x+dx});
            }
        }
    }
}
bool ok(ll mid){
    if (mid >= dist[m.first][m.second]) return false;

    for (ll i{}; i < n; i++){
        for (ll j{}; j < n; j++){
            distmecho[i][j] = 1e18;
        }
    }

    while (!q.empty()) {
        q.pop();
    }

    distmecho[m.first][m.second] = 0;
    q.push(m);

    bfs(mid);

    return ((distmecho[d.first][d.second] == (ll)1e18));
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s;
    for (ll i{}; i < n; i++){
        cin >> grid[i];
    }

    for (ll i{}; i < n; i++){
        fill(dist[i], dist[i] + cap, 1e18);
        fill(distmecho[i], distmecho[i] + cap, 1e18);
        fill(visited[i], visited[i]+cap, false);
        for (ll j{}; j < n; j++){
            if (grid[i][j] == 'M') m = {i,j};
            else if (grid[i][j] == 'H'){
                q_multi.push({i,j});
                dist[i][j] = 0;
                visited[i][j] = true;
            }
            else if (grid[i][j] == 'D') d = {i,j};       
        }        
    }

    multi_bfs();    

    ll l = 0, ans = -1;
    ll r;
    if (dist[m.first][m.second] >= (ll)1e17)
        r = (ll)n * n;   
    else
        r = dist[m.first][m.second] - 1;

    while (l <= r){
        ll mid = l + (r-l)/2;
        if (ok(mid)){
            ans = mid;
            r = mid -1;
        }
        else{
            l = mid + 1;
        }
    }
    if (ans == -1){
        cout << -1; return 0;
    }

    cout << ans;
}

• Subtask 1: 29 / 100