oj.uz

답안 #1018398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018398 2024-07-09T22:51:54 Z cryptobunny Mecho (IOI09_mecho) C++14
0 / 100
 519 ms 17932 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 / s) 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
0.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 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 340 ms 17340 KB Output isn't correct
8 Incorrect 0 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 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 Incorrect 0 ms 348 KB Output isn't correct
17 Incorrect 0 ms 344 KB Output isn't correct
18 Incorrect 0 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 0 ms 348 KB Output isn't correct
23 Incorrect 1 ms 344 KB Output isn't correct
24 Incorrect 0 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 348 KB Output isn't correct
28 Incorrect 0 ms 472 KB Output isn't correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Incorrect 1 ms 348 KB Output isn't correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Incorrect 1 ms 348 KB Output isn't correct
33 Incorrect 19 ms 3664 KB Output isn't correct
34 Incorrect 19 ms 3720 KB Output isn't correct
35 Incorrect 64 ms 3684 KB Output isn't correct
36 Incorrect 26 ms 4652 KB Output isn't correct
37 Incorrect 24 ms 4636 KB Output isn't correct
38 Incorrect 84 ms 4748 KB Output isn't correct
39 Incorrect 38 ms 5708 KB Output isn't correct
40 Incorrect 37 ms 5756 KB Output isn't correct
41 Incorrect 112 ms 5712 KB Output isn't correct
42 Incorrect 40 ms 7068 KB Output isn't correct
43 Incorrect 37 ms 7000 KB Output isn't correct
44 Incorrect 144 ms 6984 KB Output isn't correct
45 Incorrect 53 ms 8368 KB Output isn't correct
46 Incorrect 45 ms 8304 KB Output isn't correct
47 Incorrect 178 ms 8352 KB Output isn't correct
48 Incorrect 58 ms 9800 KB Output isn't correct
49 Incorrect 59 ms 9892 KB Output isn't correct
50 Incorrect 231 ms 9912 KB Output isn't correct
51 Incorrect 67 ms 11480 KB Output isn't correct
52 Incorrect 56 ms 11544 KB Output isn't correct
53 Incorrect 263 ms 11512 KB Output isn't correct
54 Incorrect 110 ms 13248 KB Output isn't correct
55 Incorrect 91 ms 13296 KB Output isn't correct
56 Incorrect 375 ms 13188 KB Output isn't correct
57 Incorrect 121 ms 15048 KB Output isn't correct
58 Incorrect 87 ms 15068 KB Output isn't correct
59 Incorrect 405 ms 15128 KB Output isn't correct
60 Incorrect 123 ms 17212 KB Output isn't correct
61 Incorrect 133 ms 17148 KB Output isn't correct
62 Incorrect 439 ms 17176 KB Output isn't correct
63 Incorrect 311 ms 17072 KB Output isn't correct
64 Incorrect 519 ms 17044 KB Output isn't correct
65 Incorrect 465 ms 16972 KB Output isn't correct
66 Incorrect 359 ms 17056 KB Output isn't correct
67 Incorrect 338 ms 16988 KB Output isn't correct
68 Incorrect 209 ms 17052 KB Output isn't correct
69 Incorrect 214 ms 17312 KB Output isn't correct
70 Incorrect 169 ms 17068 KB Output isn't correct
71 Incorrect 172 ms 17216 KB Output isn't correct
72 Incorrect 158 ms 17092 KB Output isn't correct
73 Incorrect 221 ms 17744 KB Output isn't correct
74 Incorrect 261 ms 17784 KB Output isn't correct
75 Incorrect 278 ms 17820 KB Output isn't correct
76 Incorrect 263 ms 17744 KB Output isn't correct
77 Incorrect 302 ms 17724 KB Output isn't correct
78 Incorrect 289 ms 17708 KB Output isn't correct
79 Incorrect 282 ms 17704 KB Output isn't correct
80 Incorrect 256 ms 17724 KB Output isn't correct
81 Incorrect 301 ms 17744 KB Output isn't correct
82 Incorrect 249 ms 17624 KB Output isn't correct
83 Incorrect 315 ms 17592 KB Output isn't correct
84 Incorrect 330 ms 17600 KB Output isn't correct
85 Incorrect 293 ms 17624 KB Output isn't correct
86 Incorrect 323 ms 17620 KB Output isn't correct
87 Incorrect 266 ms 17932 KB Output isn't correct
88 Incorrect 319 ms 17580 KB Output isn't correct
89 Incorrect 321 ms 17460 KB Output isn't correct
90 Incorrect 331 ms 17544 KB Output isn't correct
91 Incorrect 332 ms 17496 KB Output isn't correct
92 Incorrect 330 ms 17524 KB Output isn't correct