oj.uz

답안 #1018389

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

#define int long long

int n, s, mx, my;

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<bool>> vis(n, vector<bool>(n));
    vis[mx][my] = 1;
    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) * s <= tp.first) continue;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q.push({tp.first + 1, {nx, ny}});
            }
        }
    }
    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;
        }
    }
    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
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 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 Correct 0 ms 348 KB Output is correct
7 Incorrect 296 ms 13476 KB Output isn't correct
8 Incorrect 0 ms 344 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 476 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 2 ms 348 KB Output isn't correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 604 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Correct 1 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Correct 1 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 Correct 1 ms 348 KB Output is correct
29 Incorrect 1 ms 348 KB Output isn't correct
30 Correct 1 ms 348 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Correct 1 ms 344 KB Output is correct
33 Incorrect 11 ms 2648 KB Output isn't correct
34 Correct 11 ms 2680 KB Output is correct
35 Incorrect 61 ms 4272 KB Output isn't correct
36 Incorrect 11 ms 3420 KB Output isn't correct
37 Correct 11 ms 3316 KB Output is correct
38 Incorrect 89 ms 5952 KB Output isn't correct
39 Incorrect 17 ms 4184 KB Output isn't correct
40 Correct 14 ms 4188 KB Output is correct
41 Incorrect 105 ms 7012 KB Output isn't correct
42 Incorrect 19 ms 5416 KB Output isn't correct
43 Correct 18 ms 5208 KB Output is correct
44 Incorrect 144 ms 8204 KB Output isn't correct
45 Incorrect 21 ms 5980 KB Output isn't correct
46 Correct 21 ms 5980 KB Output is correct
47 Incorrect 174 ms 10980 KB Output isn't correct
48 Incorrect 26 ms 7072 KB Output isn't correct
49 Correct 29 ms 7260 KB Output is correct
50 Incorrect 209 ms 12440 KB Output isn't correct
51 Incorrect 27 ms 8284 KB Output isn't correct
52 Correct 28 ms 8416 KB Output is correct
53 Incorrect 258 ms 13936 KB Output isn't correct
54 Incorrect 36 ms 9556 KB Output isn't correct
55 Correct 36 ms 9552 KB Output is correct
56 Incorrect 328 ms 15528 KB Output isn't correct
57 Incorrect 37 ms 11088 KB Output isn't correct
58 Correct 44 ms 11088 KB Output is correct
59 Incorrect 334 ms 20512 KB Output isn't correct
60 Incorrect 41 ms 12376 KB Output isn't correct
61 Correct 44 ms 12372 KB Output is correct
62 Incorrect 435 ms 22780 KB Output isn't correct
63 Correct 226 ms 12732 KB Output is correct
64 Correct 324 ms 12680 KB Output is correct
65 Correct 299 ms 12784 KB Output is correct
66 Incorrect 258 ms 12920 KB Output isn't correct
67 Incorrect 266 ms 12720 KB Output isn't correct
68 Correct 147 ms 12828 KB Output is correct
69 Correct 173 ms 12740 KB Output is correct
70 Correct 152 ms 13056 KB Output is correct
71 Correct 126 ms 12820 KB Output is correct
72 Incorrect 128 ms 12788 KB Output isn't correct
73 Incorrect 108 ms 13264 KB Output isn't correct
74 Incorrect 149 ms 15672 KB Output isn't correct
75 Incorrect 141 ms 13520 KB Output isn't correct
76 Incorrect 153 ms 13488 KB Output isn't correct
77 Correct 167 ms 13496 KB Output is correct
78 Incorrect 198 ms 13568 KB Output isn't correct
79 Incorrect 244 ms 18240 KB Output isn't correct
80 Incorrect 185 ms 13584 KB Output isn't correct
81 Incorrect 154 ms 13468 KB Output isn't correct
82 Incorrect 222 ms 13864 KB Output isn't correct
83 Correct 251 ms 13340 KB Output is correct
84 Incorrect 317 ms 17716 KB Output isn't correct
85 Incorrect 245 ms 13468 KB Output isn't correct
86 Incorrect 248 ms 13420 KB Output isn't correct
87 Incorrect 267 ms 13736 KB Output isn't correct
88 Correct 286 ms 13596 KB Output is correct
89 Incorrect 289 ms 18308 KB Output isn't correct
90 Incorrect 302 ms 13596 KB Output isn't correct
91 Incorrect 294 ms 14212 KB Output isn't correct
92 Incorrect 270 ms 13360 KB Output isn't correct