oj.uz

답안 #1018400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018400 2024-07-09T22:53:37 Z cryptobunny Mecho (IOI09_mecho) C++14
29 / 100
 463 ms 17796 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) * s <= -tp.first) 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 = n * n;
    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
29.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 344 KB Output isn't correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 325 ms 17260 KB Output is 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 344 KB Output is correct
12 Incorrect 1 ms 344 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 344 KB Output isn't correct
16 Correct 1 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 0 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 0 ms 348 KB Output isn't correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Correct 0 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 344 KB Output isn't correct
30 Correct 1 ms 600 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 3612 KB Output isn't correct
34 Correct 12 ms 3648 KB Output is correct
35 Correct 65 ms 3628 KB Output is correct
36 Incorrect 20 ms 4592 KB Output isn't correct
37 Correct 17 ms 4580 KB Output is correct
38 Correct 89 ms 4664 KB Output is correct
39 Incorrect 26 ms 5696 KB Output isn't correct
40 Correct 26 ms 5752 KB Output is correct
41 Correct 123 ms 5668 KB Output is correct
42 Incorrect 31 ms 6944 KB Output isn't correct
43 Correct 25 ms 6940 KB Output is correct
44 Correct 155 ms 6920 KB Output is correct
45 Incorrect 39 ms 8344 KB Output isn't correct
46 Correct 33 ms 8276 KB Output is correct
47 Correct 190 ms 8324 KB Output is correct
48 Incorrect 46 ms 9804 KB Output isn't correct
49 Correct 47 ms 9812 KB Output is correct
50 Correct 220 ms 9828 KB Output is correct
51 Incorrect 55 ms 11436 KB Output isn't correct
52 Correct 43 ms 11340 KB Output is correct
53 Correct 266 ms 11424 KB Output is correct
54 Incorrect 65 ms 13200 KB Output isn't correct
55 Correct 66 ms 13148 KB Output is correct
56 Correct 312 ms 13092 KB Output is correct
57 Incorrect 82 ms 14996 KB Output isn't correct
58 Correct 61 ms 14972 KB Output is correct
59 Correct 375 ms 14992 KB Output is correct
60 Incorrect 94 ms 16988 KB Output isn't correct
61 Correct 100 ms 17000 KB Output is correct
62 Correct 442 ms 17028 KB Output is correct
63 Correct 271 ms 16960 KB Output is correct
64 Correct 463 ms 17008 KB Output is correct
65 Correct 374 ms 17012 KB Output is correct
66 Incorrect 340 ms 16984 KB Output isn't correct
67 Incorrect 329 ms 16992 KB Output isn't correct
68 Correct 177 ms 17260 KB Output is correct
69 Correct 155 ms 17156 KB Output is correct
70 Correct 162 ms 17036 KB Output is correct
71 Correct 153 ms 17060 KB Output is correct
72 Incorrect 141 ms 17140 KB Output isn't correct
73 Incorrect 151 ms 17796 KB Output isn't correct
74 Correct 234 ms 17672 KB Output is correct
75 Correct 274 ms 17704 KB Output is correct
76 Correct 258 ms 17680 KB Output is correct
77 Correct 296 ms 17724 KB Output is correct
78 Incorrect 295 ms 17644 KB Output isn't correct
79 Correct 212 ms 17620 KB Output is correct
80 Correct 237 ms 17664 KB Output is correct
81 Correct 270 ms 17660 KB Output is correct
82 Correct 236 ms 17640 KB Output is correct
83 Correct 296 ms 17532 KB Output is correct
84 Correct 292 ms 17552 KB Output is correct
85 Correct 292 ms 17576 KB Output is correct
86 Correct 301 ms 17504 KB Output is correct
87 Correct 292 ms 17504 KB Output is correct
88 Correct 319 ms 17376 KB Output is correct
89 Correct 322 ms 17380 KB Output is correct
90 Correct 331 ms 17384 KB Output is correct
91 Correct 297 ms 17392 KB Output is correct
92 Correct 304 ms 17376 KB Output is correct