Submission #1143012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143012		poltanos	Mecho (IOI09_mecho)	C++20	84 / 100	713 ms	24780 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define int long long

const vector<int> dx {1, -1, 0, 0};
const vector<int> dy {0, 0, 1, -1};

int n, s;
vector<string> grid(1000);
vector<vector<int>> bee_time(1000, vector<int> (1000, 1e18));
vector<vector<int>> mecho_time(1000, vector<int> (1000, 1e18));

bool inside(int x, int y, bool is_mecho, int time = 0){

    bool is_inside = (x > -1 && x < n && y > -1 && y < n && grid[x][y] != 'T');
    if(!is_inside) return false;

    if(!is_mecho) is_inside = is_inside && grid[x][y] != 'D';
    if(is_mecho) is_inside = is_mecho && bee_time[x][y] > time;

    return is_inside;
}

void calculate_bee_time(int x, int y){
    queue<pair<int, int>> q;
    q.push({x, y});
    bee_time[x][y] = 0;

    while(!q.empty()){
        auto [curr_x, curr_y] = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            int new_x = curr_x + dx[i], new_y = curr_y + dy[i];

            if(inside(new_x, new_y, false) && bee_time[new_x][new_y] > bee_time[curr_x][curr_y] + 1){
                bee_time[new_x][new_y] = bee_time[curr_x][curr_y] + 1;
                q.push({new_x, new_y});
            }
        }
    }
}

void solve(){
    cin >> n >> s;

    for(int i = 0; i < n; i++) cin >> grid[i];

    int sx, sy, ex, ey;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 'H'){
                calculate_bee_time(i, j);
            }

            if(grid[i][j] == 'M') sx = i, sy = j;
            if(grid[i][j] == 'D') ex = i, ey = j;
        }
    }

    bool possible = false;

    int lo = -1, hi = 1e9;
    while(lo < hi){
        int mid = (lo + hi + 1)/2;

        mecho_time = vector<vector<int>> (1000, vector<int> (1000, 1e18));
        mecho_time[sx][sy] = mid;
        queue<array<int, 4>> q; // { x, y, time, step # }
        q.push({sx, sy, mid, 0});

        while(!q.empty()){
            auto [curr_x, curr_y, time, step_count] = q.front();
            q.pop();


            if(++step_count >= s){
                time++;
                step_count = 0;
            }

            for(int i = 0; i < 4; i++){
                int new_x = curr_x + dx[i], new_y = curr_y + dy[i];

                if(inside(new_x, new_y, true, time) && mecho_time[new_x][new_y] > time){
                    mecho_time[new_x][new_y] = time;
                    q.push({new_x, new_y, time, step_count});
                }
            }
        }

        if(mecho_time[ex][ey] != 1e18){
            lo = mid;
            possible = true;
        }else{
            hi = mid - 1;
        }
    }

    if(!possible){
        cout << -1 << endl;
        return;
    }

    cout << lo << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    while(t--) solve();

    return 0;
}

• Subtask 1: 84 / 100