oj.uz

답안 #1018397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018397 2024-07-09T22:51:24 Z cryptobunny Mecho (IOI09_mecho) C++14
5 / 100
 425 ms 18432 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, s, mx, my, hx, hy;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool check(int t, vector<vector<char>> grid, vector<vector<int>> btime) {
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({0, {mx, my}});
    vector<vector<int>> dist(n, vector<int>(n, 0x3f3f3f3f));
    dist[mx][my] = 0;
    while (!q.empty()) {
        auto tp = q.top();
        q.pop();
        if (grid[tp.second.first][tp.second.second] == 'D') {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + tp.second.first;
            int ny = dy[i] + tp.second.second;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] == 'T' || (btime[nx][ny] - t)< -tp.first / 2) continue;
            if (dist[nx][ny] > 1 - tp.first) {
                dist[nx][ny] = 1 - tp.first;
                q.push({tp.first - 1, {nx, ny}});
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + hx;
        int ny = dy[i] + hy;
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (dist[nx][ny] != 0x3f3f3f3f) return true;
    }
    return false;
}

signed main() {
    cin >> n >> s;
    vector<vector<char>> grid(n, vector<char>(n));
    priority_queue<pair<int, pair<int, int>>> q;
    vector<vector<int>> btime(n, vector<int>(n, 0x3f3f3f3f));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'H') {
                btime[i][j] = 0;
                q.push({0, {i, j}});
            }
            if (grid[i][j] == 'M') mx = i, my = j;
            if (grid[i][j] == 'D') hx = i, hy = j;
        }
    }
    while (!q.empty()) {
        auto tp = q.top();
        q.pop();
        if (btime[tp.second.first][tp.second.second] != -tp.first) continue;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + tp.second.first;
            int ny = dy[i] + tp.second.second;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] != 'G' && grid[nx][ny] != 'M') continue;
            if (-tp.first + 1 < btime[nx][ny]) {
                btime[nx][ny] = 1 - tp.first;
                q.push({-1 + tp.first, {nx, ny}});
            }
        }
    }

    int l = 0;
    int r = 1e9 + 1;
    while (l != r) {
        int mid = (l + r + 1)/2;
        if (check(mid, grid, btime)) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    cout << l << endl;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 600 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 209 ms 18020 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 1 ms 468 KB Output isn't correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Incorrect 1 ms 344 KB Output isn't correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Incorrect 1 ms 348 KB Output isn't correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Incorrect 1 ms 348 KB Output isn't correct
27 Incorrect 1 ms 560 KB Output isn't correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Incorrect 1 ms 348 KB Output isn't correct
30 Incorrect 1 ms 348 KB Output isn't correct
31 Incorrect 1 ms 344 KB Output isn't correct
32 Incorrect 1 ms 348 KB Output isn't correct
33 Incorrect 26 ms 3804 KB Output isn't correct
34 Incorrect 20 ms 3796 KB Output isn't correct
35 Incorrect 37 ms 3820 KB Output isn't correct
36 Incorrect 29 ms 4804 KB Output isn't correct
37 Incorrect 25 ms 4784 KB Output isn't correct
38 Incorrect 49 ms 4792 KB Output isn't correct
39 Incorrect 41 ms 6092 KB Output isn't correct
40 Incorrect 38 ms 6044 KB Output isn't correct
41 Incorrect 61 ms 6036 KB Output isn't correct
42 Incorrect 44 ms 7316 KB Output isn't correct
43 Incorrect 47 ms 7228 KB Output isn't correct
44 Incorrect 75 ms 7264 KB Output isn't correct
45 Incorrect 56 ms 8672 KB Output isn't correct
46 Incorrect 46 ms 8640 KB Output isn't correct
47 Incorrect 93 ms 8708 KB Output isn't correct
48 Incorrect 64 ms 10192 KB Output isn't correct
49 Incorrect 69 ms 10160 KB Output isn't correct
50 Incorrect 133 ms 10244 KB Output isn't correct
51 Incorrect 75 ms 11908 KB Output isn't correct
52 Incorrect 65 ms 11956 KB Output isn't correct
53 Incorrect 128 ms 11876 KB Output isn't correct
54 Incorrect 99 ms 13692 KB Output isn't correct
55 Incorrect 129 ms 13584 KB Output isn't correct
56 Incorrect 156 ms 13848 KB Output isn't correct
57 Incorrect 110 ms 15608 KB Output isn't correct
58 Incorrect 92 ms 15596 KB Output isn't correct
59 Incorrect 203 ms 15728 KB Output isn't correct
60 Incorrect 123 ms 17672 KB Output isn't correct
61 Incorrect 118 ms 17772 KB Output isn't correct
62 Incorrect 203 ms 17744 KB Output isn't correct
63 Incorrect 295 ms 17644 KB Output isn't correct
64 Incorrect 339 ms 17700 KB Output isn't correct
65 Incorrect 425 ms 17664 KB Output isn't correct
66 Incorrect 311 ms 17632 KB Output isn't correct
67 Incorrect 349 ms 17680 KB Output isn't correct
68 Correct 191 ms 17816 KB Output is correct
69 Incorrect 164 ms 17856 KB Output isn't correct
70 Incorrect 158 ms 17700 KB Output isn't correct
71 Incorrect 176 ms 17728 KB Output isn't correct
72 Incorrect 173 ms 17696 KB Output isn't correct
73 Incorrect 171 ms 18412 KB Output isn't correct
74 Incorrect 179 ms 18376 KB Output isn't correct
75 Incorrect 190 ms 18396 KB Output isn't correct
76 Incorrect 187 ms 18432 KB Output isn't correct
77 Incorrect 203 ms 18324 KB Output isn't correct
78 Incorrect 202 ms 18428 KB Output isn't correct
79 Incorrect 189 ms 18340 KB Output isn't correct
80 Incorrect 159 ms 18264 KB Output isn't correct
81 Incorrect 188 ms 18412 KB Output isn't correct
82 Incorrect 183 ms 18296 KB Output isn't correct
83 Correct 185 ms 18208 KB Output is correct
84 Incorrect 176 ms 18292 KB Output isn't correct
85 Incorrect 162 ms 18288 KB Output isn't correct
86 Incorrect 179 ms 18212 KB Output isn't correct
87 Incorrect 188 ms 18184 KB Output isn't correct
88 Correct 170 ms 18160 KB Output is correct
89 Incorrect 145 ms 18140 KB Output isn't correct
90 Incorrect 194 ms 18280 KB Output isn't correct
91 Incorrect 175 ms 18164 KB Output isn't correct
92 Incorrect 190 ms 18092 KB Output isn't correct