oj.uz

답안 #1018391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018391 2024-07-09T22:19:05 Z cryptobunny Mecho (IOI09_mecho) C++14
13 / 100
 423 ms 22424 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
13.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 303 ms 13448 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is 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 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 1 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 0 ms 348 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 1 ms 348 KB Output is correct
21 Incorrect 1 ms 344 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 2796 KB Output isn't correct
34 Correct 9 ms 2652 KB Output is correct
35 Incorrect 64 ms 4240 KB Output isn't correct
36 Incorrect 11 ms 3416 KB Output isn't correct
37 Correct 11 ms 3420 KB Output is correct
38 Incorrect 122 ms 5992 KB Output isn't correct
39 Incorrect 15 ms 4184 KB Output isn't correct
40 Correct 14 ms 4188 KB Output is correct
41 Incorrect 113 ms 7032 KB Output isn't correct
42 Incorrect 18 ms 5212 KB Output isn't correct
43 Correct 20 ms 5208 KB Output is correct
44 Incorrect 153 ms 8188 KB Output isn't correct
45 Incorrect 21 ms 5976 KB Output isn't correct
46 Correct 22 ms 6116 KB Output is correct
47 Incorrect 197 ms 11032 KB Output isn't correct
48 Incorrect 24 ms 7256 KB Output isn't correct
49 Correct 26 ms 7256 KB Output is correct
50 Incorrect 240 ms 12368 KB Output isn't correct
51 Incorrect 27 ms 8284 KB Output isn't correct
52 Correct 27 ms 8280 KB Output is correct
53 Incorrect 247 ms 14008 KB Output isn't correct
54 Incorrect 37 ms 9564 KB Output isn't correct
55 Correct 35 ms 9556 KB Output is correct
56 Incorrect 317 ms 15504 KB Output isn't correct
57 Incorrect 47 ms 11092 KB Output isn't correct
58 Correct 39 ms 11096 KB Output is correct
59 Incorrect 393 ms 20472 KB Output isn't correct
60 Incorrect 44 ms 12376 KB Output isn't correct
61 Correct 44 ms 12392 KB Output is correct
62 Incorrect 423 ms 22424 KB Output isn't correct
63 Incorrect 250 ms 12676 KB Output isn't correct
64 Correct 325 ms 12768 KB Output is correct
65 Incorrect 303 ms 12704 KB Output isn't correct
66 Incorrect 258 ms 12672 KB Output isn't correct
67 Incorrect 260 ms 12660 KB Output isn't correct
68 Correct 156 ms 12760 KB Output is correct
69 Correct 148 ms 12772 KB Output is correct
70 Correct 174 ms 12764 KB Output is correct
71 Correct 145 ms 12868 KB Output is correct
72 Incorrect 133 ms 12924 KB Output isn't correct
73 Incorrect 116 ms 13256 KB Output isn't correct
74 Incorrect 148 ms 15724 KB Output isn't correct
75 Correct 155 ms 13556 KB Output is correct
76 Incorrect 164 ms 13300 KB Output isn't correct
77 Correct 171 ms 13556 KB Output is correct
78 Incorrect 207 ms 13532 KB Output isn't correct
79 Incorrect 245 ms 18184 KB Output isn't correct
80 Incorrect 185 ms 13556 KB Output isn't correct
81 Incorrect 159 ms 13424 KB Output isn't correct
82 Incorrect 222 ms 14016 KB Output isn't correct
83 Correct 253 ms 13312 KB Output is correct
84 Incorrect 287 ms 17728 KB Output isn't correct
85 Incorrect 215 ms 13424 KB Output isn't correct
86 Incorrect 235 ms 13416 KB Output isn't correct
87 Incorrect 278 ms 13692 KB Output isn't correct
88 Correct 244 ms 13308 KB Output is correct
89 Incorrect 287 ms 18624 KB Output isn't correct
90 Incorrect 290 ms 13652 KB Output isn't correct
91 Incorrect 306 ms 14320 KB Output isn't correct
92 Incorrect 273 ms 13788 KB Output isn't correct