Submission #386520

# Submission time Handle Problem Language Result Execution time Memory
386520 2021-04-06T17:44:37 Z SansPapyrus683 Mecho (IOI09_mecho) C++17
21 / 100
1000 ms 65540 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 27 ms 1004 KB Output is correct
7 Runtime error 535 ms 65540 KB Execution killed with signal 9
8 Correct 1 ms 492 KB Output is correct
9 Runtime error 601 ms 65540 KB Execution killed with signal 9
10 Correct 140 ms 3692 KB Output is correct
11 Correct 23 ms 1644 KB Output is correct
12 Incorrect 2 ms 364 KB Output isn't correct
13 Runtime error 519 ms 65540 KB Execution killed with signal 9
14 Runtime error 610 ms 65540 KB Execution killed with signal 9
15 Correct 1 ms 364 KB Output is correct
16 Execution timed out 1090 ms 55504 KB Time limit exceeded
17 Correct 1 ms 364 KB Output is correct
18 Runtime error 928 ms 65540 KB Execution killed with signal 9
19 Correct 2 ms 492 KB Output is correct
20 Runtime error 847 ms 65540 KB Execution killed with signal 9
21 Correct 1 ms 364 KB Output is correct
22 Runtime error 913 ms 65540 KB Execution killed with signal 9
23 Correct 1 ms 364 KB Output is correct
24 Runtime error 864 ms 65540 KB Execution killed with signal 9
25 Correct 2 ms 364 KB Output is correct
26 Runtime error 910 ms 65540 KB Execution killed with signal 9
27 Correct 2 ms 364 KB Output is correct
28 Runtime error 932 ms 65540 KB Execution killed with signal 9
29 Correct 2 ms 364 KB Output is correct
30 Runtime error 850 ms 65540 KB Execution killed with signal 9
31 Correct 2 ms 364 KB Output is correct
32 Runtime error 908 ms 65536 KB Execution killed with signal 9
33 Correct 18 ms 1732 KB Output is correct
34 Runtime error 846 ms 65540 KB Execution killed with signal 9
35 Runtime error 852 ms 65540 KB Execution killed with signal 9
36 Correct 25 ms 2156 KB Output is correct
37 Runtime error 883 ms 65540 KB Execution killed with signal 9
38 Runtime error 876 ms 65540 KB Execution killed with signal 9
39 Correct 30 ms 2612 KB Output is correct
40 Runtime error 860 ms 65540 KB Execution killed with signal 9
41 Runtime error 863 ms 65540 KB Execution killed with signal 9
42 Correct 40 ms 3204 KB Output is correct
43 Runtime error 890 ms 65540 KB Execution killed with signal 9
44 Runtime error 867 ms 65540 KB Execution killed with signal 9
45 Correct 46 ms 3772 KB Output is correct
46 Runtime error 859 ms 65540 KB Execution killed with signal 9
47 Runtime error 880 ms 65540 KB Execution killed with signal 9
48 Correct 55 ms 4348 KB Output is correct
49 Runtime error 875 ms 65536 KB Execution killed with signal 9
50 Runtime error 874 ms 65540 KB Execution killed with signal 9
51 Correct 63 ms 5084 KB Output is correct
52 Runtime error 849 ms 65540 KB Execution killed with signal 9
53 Runtime error 880 ms 65540 KB Execution killed with signal 9
54 Correct 75 ms 5844 KB Output is correct
55 Runtime error 890 ms 65540 KB Execution killed with signal 9
56 Runtime error 887 ms 65540 KB Execution killed with signal 9
57 Correct 89 ms 6604 KB Output is correct
58 Runtime error 881 ms 65540 KB Execution killed with signal 9
59 Runtime error 911 ms 65536 KB Execution killed with signal 9
60 Correct 99 ms 7544 KB Output is correct
61 Runtime error 879 ms 65540 KB Execution killed with signal 9
62 Runtime error 891 ms 65536 KB Execution killed with signal 9
63 Runtime error 878 ms 65540 KB Execution killed with signal 9
64 Runtime error 876 ms 65540 KB Execution killed with signal 9
65 Runtime error 890 ms 65540 KB Execution killed with signal 9
66 Runtime error 876 ms 65536 KB Execution killed with signal 9
67 Runtime error 873 ms 65540 KB Execution killed with signal 9
68 Execution timed out 1016 ms 65540 KB Time limit exceeded
69 Execution timed out 1006 ms 65540 KB Time limit exceeded
70 Execution timed out 1020 ms 65540 KB Time limit exceeded
71 Execution timed out 1012 ms 65540 KB Time limit exceeded
72 Runtime error 823 ms 65536 KB Execution killed with signal 9
73 Runtime error 538 ms 65540 KB Execution killed with signal 9
74 Runtime error 546 ms 65540 KB Execution killed with signal 9
75 Runtime error 543 ms 65540 KB Execution killed with signal 9
76 Runtime error 539 ms 65540 KB Execution killed with signal 9
77 Runtime error 541 ms 65540 KB Execution killed with signal 9
78 Runtime error 582 ms 65540 KB Execution killed with signal 9
79 Runtime error 530 ms 65536 KB Execution killed with signal 9
80 Runtime error 534 ms 65540 KB Execution killed with signal 9
81 Runtime error 595 ms 65540 KB Execution killed with signal 9
82 Runtime error 549 ms 65540 KB Execution killed with signal 9
83 Runtime error 567 ms 65540 KB Execution killed with signal 9
84 Runtime error 564 ms 65540 KB Execution killed with signal 9
85 Runtime error 636 ms 65540 KB Execution killed with signal 9
86 Runtime error 539 ms 65540 KB Execution killed with signal 9
87 Runtime error 558 ms 65540 KB Execution killed with signal 9
88 Runtime error 538 ms 65540 KB Execution killed with signal 9
89 Runtime error 556 ms 65540 KB Execution killed with signal 9
90 Runtime error 540 ms 65540 KB Execution killed with signal 9
91 Runtime error 537 ms 65540 KB Execution killed with signal 9
92 Runtime error 569 ms 65536 KB Execution killed with signal 9