Submission #1284627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284627		srittheboss	Mecho (IOI09_mecho)	C++17	53 / 100	157 ms	6444 KiB

mecho

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

int main() {
    int n, s;
    cin >> n >> s;
    vector<vector<char>> board(n, vector<char>(n));

    vector<pair<int, int>> hives;
    pair<int, int> mecho;
    pair<int, int> home;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'H') {
                hives.push_back({i, j});
            } else if (board[i][j] == 'M') {
                mecho = {i, j};
            } else if (board[i][j] == 'D') {
                home = {i, j};
            }
        }
    }

    vector<vector<int>> hive_dist(n, vector<int>(n, 1e8));
    vector<vector<bool>> hive_visited(n, vector<bool>(n, false));
    queue<pair<int, int>> hive_queue;
    for (auto hive : hives) {
        hive_queue.push(hive);
        hive_dist[hive.first][hive.second] = 0;
        hive_visited[hive.first][hive.second] = true;
    }

    vector<pair<int, int>> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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

        for (auto move : moves) {
            pair<int, int> next_hive = {curr_hive.first + move.first, curr_hive.second + move.second};
            if (0 <= next_hive.first && 0 <= next_hive.second && next_hive.first < n && next_hive.second < n) {
                if (!hive_visited[next_hive.first][next_hive.second]) {
                    if (board[next_hive.first][next_hive.second] != 'T' && board[next_hive.first][next_hive.second] != 'D') {
                        hive_dist[next_hive.first][next_hive.second] = hive_dist[curr_hive.first][curr_hive.second] + 1;
                        hive_queue.push({next_hive.first, next_hive.second});
                        hive_visited[next_hive.first][next_hive.second] = true;
                    }
                }
            }
        }

    }

    int lo = -1, hi = 1000;

    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        vector<vector<int>> mecho_dist(n, vector<int>(n, 1e8));
        vector<vector<bool>> mecho_visited(n, vector<bool>(n, false));

        queue<pair<int, int>> q;
        q.push(mecho);
        mecho_dist[mecho.first][mecho.second] = 0;
        mecho_visited[mecho.first][mecho.second] = true;

        bool valid = false;

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

            if (p == home) {
                valid = true;
                break;
            }

            for (pair<int, int> move : moves) {
                pair<int, int> next_p = {p.first + move.first, p.second + move.second};

                if (0 <= next_p.first && next_p.first < n && 0 <= next_p.second && next_p.second < n) {
                    if (!mecho_visited[next_p.first][next_p.second]) {
                        if (board[next_p.first][next_p.second] != 'T') {
                            if (hive_dist[next_p.first][next_p.second] - mid > (mecho_dist[p.first][p.second]+1) / s) {
                                q.push(next_p);
                                mecho_dist[next_p.first][next_p.second] = mecho_dist[p.first][p.second] + 1;
                                mecho_visited[next_p.first][next_p.second] = true;
                            }
                        }
                    }
                }
            }
        }

        if (valid) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }

    cout << lo << endl;

}

• Subtask 1: 53 / 100