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

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.0 / 100.0

#	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