Submission #386520

#	Time	Username	Problem	Language	Result	Execution time	Memory
386520		SansPapyrus683	Mecho (IOI09_mecho)	C++17	21 / 100	1090 ms	65540 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using std::cout;
using std::endl;
using std::vector;
using std::pair;

vector<pair<int, int>> neighbors(const pair<int, int>& at, int row_num, int col_num) {
    vector<pair<int, int>> neighbors;
    if (at.first > 0) {
        neighbors.push_back({at.first - 1, at.second});
    }
    if (at.second > 0) {
        neighbors.push_back({at.first, at.second - 1});
    }
    if (at.first < row_num - 1) {
        neighbors.push_back({at.first + 1, at.second});
    }
    if (at.second < col_num - 1) {
        neighbors.push_back({at.first, at.second + 1});
    }
    return neighbors;
}

class Field {
    private:
        const vector<vector<char>> field;
        const int row_num;
        const int col_num;
        pair<int, int> start;
        vector<vector<int>> bee_dists;
    public:
        Field(const vector<vector<char>>& field)
                : field(field), row_num(field.size()), col_num(field[0].size()),
                  bee_dists(row_num, vector<int>(col_num, INT_MAX)) {
            std::queue<pair<int, int>> frontier;
            for (int r = 0; r < row_num; r++) {
                for (int c = 0; c < col_num; c++) {
                    if (field[r][c] == 'H') {
                        frontier.push({r, c});
                        bee_dists[r][c] = 0;
                    } else if (field[r][c] == 'M') {
                        start = {r, c};
                    }
                }
            }
            while (!frontier.empty()) {
                pair<int, int> c = frontier.front();  // c for curr and to reduce my line length
                frontier.pop();
                int n_cost = bee_dists[c.first][c.second] + 1;
                for (const pair<int, int>& n : neighbors(c, row_num, col_num)) {
                    if (n_cost < bee_dists[n.first][n.second]
                            && field[n.first][n.second] != 'T'
                            && field[n.first][n.second] != 'D') {
                        bee_dists[n.first][n.second] = n_cost;
                        frontier.push(n);
                    }
                }
            }
        }

        bool can_go_home(int honey_time, int speed) {
            std::queue<pair<int, int>> frontier;
            vector<vector<int>> min_moves(row_num, vector<int>(col_num, INT_MAX));
            frontier.push(start);
            min_moves[start.first][start.second] = honey_time * speed;
            while (!frontier.empty()) {
                pair<int, int> curr = frontier.front();
                frontier.pop();
                if (field[curr.first][curr.second] == 'D') {
                    return true;
                }
                int n_cost = min_moves[curr.first][curr.second] + 1;
                for (const pair<int, int>& n : neighbors(curr, row_num, col_num)) {
                    if (field[n.first][n.second] != 'T' && (n_cost / speed) < bee_dists[n.first][n.second]) {
                        min_moves[n.first][n.second] = n_cost;
                        frontier.push(n);
                    }
                }
            }
            return false;
        }
};

// https://oj.uz/problem/view/IOI09_mecho (sample input ommitted)
int main() {
    int side_len;
    int speed;
    std::cin >> side_len >> speed;
    vector<vector<char>> grid(side_len, vector<char>(side_len));
    for (int r = 0; r < side_len; r++) {
        for (int c = 0; c < side_len; c++) {
            std::cin >> grid[r][c];
        }
    }

    Field field(grid);
    int lo = 0;
    int hi = side_len * side_len;
    int valid = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (field.can_go_home(mid, speed)) {
            valid = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << valid << endl;
}

• Subtask 1: 21 / 100