oj.uz

답안 #1018390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018390 2024-07-09T22:16:43 Z cryptobunny Mecho (IOI09_mecho) C++14
13 / 100
 419 ms 21824 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 0 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 0 ms 348 KB Output is correct
7 Incorrect 291 ms 12848 KB Output isn't correct
8 Incorrect 1 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 1 ms 344 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 1 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 0 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Correct 1 ms 344 KB Output is correct
25 Incorrect 1 ms 504 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 600 KB Output isn't correct
28 Correct 1 ms 344 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 348 KB Output is correct
33 Incorrect 12 ms 2676 KB Output isn't correct
34 Correct 12 ms 2928 KB Output is correct
35 Incorrect 64 ms 4088 KB Output isn't correct
36 Incorrect 11 ms 3164 KB Output isn't correct
37 Correct 11 ms 3352 KB Output is correct
38 Incorrect 89 ms 5800 KB Output isn't correct
39 Incorrect 14 ms 3928 KB Output isn't correct
40 Correct 13 ms 3932 KB Output is correct
41 Incorrect 111 ms 6760 KB Output isn't correct
42 Incorrect 19 ms 4952 KB Output isn't correct
43 Correct 19 ms 4956 KB Output is correct
44 Incorrect 153 ms 7892 KB Output isn't correct
45 Incorrect 19 ms 5720 KB Output isn't correct
46 Correct 23 ms 5724 KB Output is correct
47 Incorrect 182 ms 10624 KB Output isn't correct
48 Incorrect 24 ms 6744 KB Output isn't correct
49 Correct 29 ms 6748 KB Output is correct
50 Incorrect 207 ms 12048 KB Output isn't correct
51 Incorrect 28 ms 8028 KB Output isn't correct
52 Correct 26 ms 8068 KB Output is correct
53 Incorrect 228 ms 13592 KB Output isn't correct
54 Incorrect 37 ms 9048 KB Output isn't correct
55 Correct 35 ms 9044 KB Output is correct
56 Incorrect 310 ms 15120 KB Output isn't correct
57 Incorrect 35 ms 10544 KB Output isn't correct
58 Correct 37 ms 10324 KB Output is correct
59 Incorrect 370 ms 20220 KB Output isn't correct
60 Incorrect 42 ms 11856 KB Output isn't correct
61 Correct 41 ms 11760 KB Output is correct
62 Incorrect 419 ms 21824 KB Output isn't correct
63 Incorrect 231 ms 12084 KB Output isn't correct
64 Correct 282 ms 12092 KB Output is correct
65 Incorrect 284 ms 12232 KB Output isn't correct
66 Incorrect 273 ms 12096 KB Output isn't correct
67 Incorrect 270 ms 12184 KB Output isn't correct
68 Correct 142 ms 12180 KB Output is correct
69 Correct 184 ms 12124 KB Output is correct
70 Correct 142 ms 12192 KB Output is correct
71 Correct 138 ms 12164 KB Output is correct
72 Incorrect 129 ms 12096 KB Output isn't correct
73 Incorrect 110 ms 12744 KB Output isn't correct
74 Incorrect 144 ms 15216 KB Output isn't correct
75 Correct 145 ms 12748 KB Output is correct
76 Incorrect 153 ms 12752 KB Output isn't correct
77 Correct 180 ms 13108 KB Output is correct
78 Incorrect 198 ms 12896 KB Output isn't correct
79 Incorrect 262 ms 17652 KB Output isn't correct
80 Incorrect 188 ms 12904 KB Output isn't correct
81 Incorrect 159 ms 12768 KB Output isn't correct
82 Incorrect 220 ms 13236 KB Output isn't correct
83 Correct 266 ms 12840 KB Output is correct
84 Incorrect 288 ms 17084 KB Output isn't correct
85 Incorrect 222 ms 12812 KB Output isn't correct
86 Incorrect 222 ms 12808 KB Output isn't correct
87 Incorrect 288 ms 13096 KB Output isn't correct
88 Correct 251 ms 12740 KB Output is correct
89 Incorrect 305 ms 17704 KB Output isn't correct
90 Incorrect 300 ms 13016 KB Output isn't correct
91 Incorrect 317 ms 13572 KB Output isn't correct
92 Incorrect 269 ms 12740 KB Output isn't correct