Submission #1269144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269144		vk3601h	Mecho (IOI09_mecho)	C++20	100 / 100	261 ms	6644 KiB

mecho

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, S;
    cin >> N >> S;

    pair<int, int> mecho_init_pos, mecho_home_pos;
    vector<pair<int, int>> hives;

    vector<string> grid(N);
    for (int i = 0; i < N; ++i){
        cin >> grid[i];
        for (int j = 0; j < N; ++j){
            if (grid[i][j] == 'M') mecho_init_pos = {i, j};
            if (grid[i][j] == 'D') mecho_home_pos = {i, j};
            if (grid[i][j] == 'H') hives.push_back({i, j});
        }
    }

    auto adjacent_node = [&](const pair<int, int> &init_pos, bool is_bear) -> vector<pair<int, int>>{
        vector<pair<int, int>> adj;
        if (init_pos.first > 0 && grid[init_pos.first - 1][init_pos.second] != 'T' && (is_bear || grid[init_pos.first - 1][init_pos.second] != 'D')) adj.push_back({init_pos.first - 1, init_pos.second});
        if (init_pos.second > 0 && grid[init_pos.first][init_pos.second - 1] != 'T' && (is_bear || grid[init_pos.first][init_pos.second - 1] != 'D')) adj.push_back({init_pos.first, init_pos.second - 1});
        if (init_pos.first < N - 1 && grid[init_pos.first + 1][init_pos.second] != 'T' && (is_bear || grid[init_pos.first + 1][init_pos.second] != 'D')) adj.push_back({init_pos.first + 1, init_pos.second});
        if (init_pos.second < N - 1 && grid[init_pos.first][init_pos.second + 1] != 'T' && (is_bear || grid[init_pos.first][init_pos.second + 1] != 'D')) adj.push_back({init_pos.first, init_pos.second + 1});
        return adj;
    };

    vector<vector<int>> dist_bee(N, vector<int>(N, INT_MAX));
    queue<pair<int, int>> frontier_bee;
    for (pair<int, int> h : hives){
        dist_bee[h.first][h.second] = 0;
        frontier_bee.push(h);
    }

    while (!frontier_bee.empty()){
        pair<int, int> curr = frontier_bee.front();
        frontier_bee.pop();
        for (pair<int, int> nxt : adjacent_node(curr, false)){
            if (dist_bee[curr.first][curr.second] + S < dist_bee[nxt.first][nxt.second]){
                dist_bee[nxt.first][nxt.second] = dist_bee[curr.first][curr.second] + S;
                frontier_bee.push(nxt);
            }
        }
    }

    auto check = [&](int res) -> bool{
        if (dist_bee[mecho_init_pos.first][mecho_init_pos.second] <= res * S) return false;

        bool valid = false;
        vector<vector<int>> dist_mecho(N, vector<int>(N, INT_MAX));
        queue<pair<int, int>> frontier_mecho;
        dist_mecho[mecho_init_pos.first][mecho_init_pos.second] = res * S;
        frontier_mecho.push(mecho_init_pos);

        while (!frontier_mecho.empty()){
            pair<int, int> curr = frontier_mecho.front();
            frontier_mecho.pop();

            if (curr == mecho_home_pos){
                valid = true;
                break;
            }

            for (pair<int, int> nxt : adjacent_node(curr, true)){
                if (dist_mecho[curr.first][curr.second] + 1 < dist_mecho[nxt.first][nxt.second] && dist_mecho[curr.first][curr.second] + 1 < dist_bee[nxt.first][nxt.second]){
                    dist_mecho[nxt.first][nxt.second] = dist_mecho[curr.first][curr.second] + 1;
                    frontier_mecho.push(nxt);
                }
            }
        }

        return valid;
    };

    int l = 0, r = 640000, ans = -1;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    cout << ans;

    return 0;
}

• Subtask 1: 100 / 100