oj.uz

Submission #1018402

# Submission time Handle Problem Language Result Execution time Memory
1018402 2024-07-09T22:54:47 Z cryptobunny Mecho (IOI09_mecho) C++14
40 / 100
 460 ms 17780 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;
    if (btime[mx][my] <= t) q.pop();
    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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 0 ms 344 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 1 ms 348 KB Output is correct
7 Correct 344 ms 17264 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 1 ms 344 KB Output isn't correct
16 Correct 0 ms 436 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 1 ms 452 KB Output isn't correct
20 Correct 1 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Correct 1 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 1 ms 348 KB Output is correct
27 Incorrect 0 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 3616 KB Output isn't correct
34 Correct 12 ms 3600 KB Output is correct
35 Correct 67 ms 3616 KB Output is correct
36 Incorrect 19 ms 4604 KB Output isn't correct
37 Correct 18 ms 4588 KB Output is correct
38 Correct 93 ms 4604 KB Output is correct
39 Incorrect 26 ms 5696 KB Output isn't correct
40 Correct 27 ms 5732 KB Output is correct
41 Correct 122 ms 5672 KB Output is correct
42 Incorrect 31 ms 6952 KB Output isn't correct
43 Correct 35 ms 6940 KB Output is correct
44 Correct 152 ms 6912 KB Output is correct
45 Incorrect 51 ms 8408 KB Output isn't correct
46 Correct 31 ms 8260 KB Output is correct
47 Correct 181 ms 8320 KB Output is correct
48 Incorrect 48 ms 9748 KB Output isn't correct
49 Correct 59 ms 9780 KB Output is correct
50 Correct 230 ms 9760 KB Output is correct
51 Incorrect 57 ms 11392 KB Output isn't correct
52 Correct 43 ms 11356 KB Output is correct
53 Correct 272 ms 11384 KB Output is correct
54 Incorrect 72 ms 13264 KB Output isn't correct
55 Correct 71 ms 13224 KB Output is correct
56 Correct 343 ms 13104 KB Output is correct
57 Incorrect 78 ms 15076 KB Output isn't correct
58 Correct 83 ms 14956 KB Output is correct
59 Correct 384 ms 15056 KB Output is correct
60 Incorrect 88 ms 17024 KB Output isn't correct
61 Correct 111 ms 16944 KB Output is correct
62 Correct 426 ms 16964 KB Output is correct
63 Correct 259 ms 16932 KB Output is correct
64 Correct 460 ms 17084 KB Output is correct
65 Correct 385 ms 17140 KB Output is correct
66 Incorrect 319 ms 16928 KB Output isn't correct
67 Incorrect 294 ms 17080 KB Output isn't correct
68 Correct 174 ms 17084 KB Output is correct
69 Correct 145 ms 17124 KB Output is correct
70 Correct 166 ms 17024 KB Output is correct
71 Correct 164 ms 17064 KB Output is correct
72 Correct 140 ms 17044 KB Output is correct
73 Correct 159 ms 17756 KB Output is correct
74 Correct 241 ms 17680 KB Output is correct
75 Correct 229 ms 17720 KB Output is correct
76 Correct 219 ms 17772 KB Output is correct
77 Correct 234 ms 17708 KB Output is correct
78 Incorrect 267 ms 17780 KB Output isn't correct
79 Correct 179 ms 17640 KB Output is correct
80 Correct 220 ms 17636 KB Output is correct
81 Correct 278 ms 17644 KB Output is correct
82 Correct 242 ms 17652 KB Output is correct
83 Correct 302 ms 17552 KB Output is correct
84 Correct 303 ms 17560 KB Output is correct
85 Correct 282 ms 17536 KB Output is correct
86 Correct 321 ms 17544 KB Output is correct
87 Correct 284 ms 17476 KB Output is correct
88 Correct 332 ms 17560 KB Output is correct
89 Correct 344 ms 17388 KB Output is correct
90 Correct 343 ms 17420 KB Output is correct
91 Correct 303 ms 17380 KB Output is correct
92 Correct 333 ms 17408 KB Output is correct