Submission #1283650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283650		srittheboss	Mecho (IOI09_mecho)	C++17	2 / 100	764 ms	131072 KiB

mecho

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

bool test(vector<vector<char>> &board, vector<vector<int>> &hive_dist, vector<vector<int>> &mecho_dist, pair<int, int> mecho, pair<int, int> home, int n, int s, int t) {
    queue<pair<int, int>> q;
    q.push(mecho);

    vector<pair<int, int>> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    vector<vector<bool>> visited(n, vector<bool>(n, false));

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

        if (p == home) {
            return true;
        }
        visited[p.first][p.second] = true;

        for (auto move: moves) {
            pair<int, int> new_p = {p.first + move.first, p.second + move.second};
            if (0 <= new_p.first && new_p.first < n && 0 <= new_p.second && new_p.second < n) {
                if (board[new_p.first][new_p.second] != 'T') {
                    if (hive_dist[new_p.first][new_p.second] - t - 1 > mecho_dist[new_p.first][new_p.second] / s) {
                        if (!visited[new_p.first][new_p.second]) {
                            q.push(new_p);
                        }
                    }
                }
            }
        }


    }

    return false;
}

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;
    }

    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();

        hive_visited[curr_hive.first][curr_hive.second] = true;

        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});
                    }
                }
            }
        }

    }

    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;

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        mecho_visited[p.first][p.second] = true;

        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') {

                        q.push(next_p);
                        mecho_dist[next_p.first][next_p.second] = mecho_dist[p.first][p.second] + 1;

                    }
                }
            }
        }
    }



    int lo = -1, hi = 1000;

    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (test(board, hive_dist, mecho_dist, mecho, home, n, s, mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }

    cout << lo << endl;

}

• Subtask 1: 2 / 100