oj.uz

답안 #1018399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018399 2024-07-09T22:52:32 Z cryptobunny Mecho (IOI09_mecho) C++14
0 / 100
 377 ms 21700 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) < tp.first / s) 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
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 1 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 309 ms 12864 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 1 ms 344 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 348 KB Output isn't correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Incorrect 1 ms 600 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 1 ms 348 KB Output isn't correct
29 Incorrect 1 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 10 ms 2676 KB Output isn't correct
34 Incorrect 9 ms 2564 KB Output isn't correct
35 Correct 56 ms 4172 KB Output is correct
36 Incorrect 11 ms 3160 KB Output isn't correct
37 Incorrect 11 ms 3164 KB Output isn't correct
38 Correct 82 ms 5824 KB Output is correct
39 Incorrect 15 ms 3928 KB Output isn't correct
40 Incorrect 14 ms 4112 KB Output isn't correct
41 Correct 93 ms 6840 KB Output is correct
42 Incorrect 18 ms 4956 KB Output isn't correct
43 Incorrect 19 ms 4724 KB Output isn't correct
44 Correct 137 ms 7932 KB Output is correct
45 Incorrect 26 ms 5724 KB Output isn't correct
46 Incorrect 21 ms 5720 KB Output isn't correct
47 Correct 162 ms 10744 KB Output is correct
48 Incorrect 24 ms 6744 KB Output isn't correct
49 Incorrect 25 ms 7000 KB Output isn't correct
50 Correct 204 ms 11984 KB Output is correct
51 Incorrect 29 ms 8020 KB Output isn't correct
52 Incorrect 28 ms 8028 KB Output isn't correct
53 Correct 217 ms 13552 KB Output is correct
54 Incorrect 37 ms 9160 KB Output isn't correct
55 Incorrect 36 ms 9052 KB Output isn't correct
56 Correct 299 ms 15052 KB Output is correct
57 Incorrect 38 ms 10312 KB Output isn't correct
58 Incorrect 38 ms 10324 KB Output isn't correct
59 Correct 365 ms 19972 KB Output is correct
60 Incorrect 42 ms 11864 KB Output isn't correct
61 Incorrect 41 ms 11860 KB Output isn't correct
62 Correct 377 ms 21700 KB Output is correct
63 Incorrect 258 ms 12156 KB Output isn't correct
64 Incorrect 284 ms 12084 KB Output isn't correct
65 Incorrect 307 ms 12048 KB Output isn't correct
66 Incorrect 270 ms 12052 KB Output isn't correct
67 Incorrect 246 ms 12004 KB Output isn't correct
68 Incorrect 150 ms 12176 KB Output isn't correct
69 Incorrect 152 ms 12120 KB Output isn't correct
70 Incorrect 164 ms 12240 KB Output isn't correct
71 Incorrect 128 ms 12184 KB Output isn't correct
72 Incorrect 128 ms 12180 KB Output isn't correct
73 Incorrect 109 ms 12676 KB Output isn't correct
74 Correct 169 ms 15092 KB Output is correct
75 Correct 147 ms 12744 KB Output is correct
76 Correct 169 ms 12664 KB Output is correct
77 Incorrect 176 ms 12996 KB Output isn't correct
78 Incorrect 196 ms 12916 KB Output isn't correct
79 Incorrect 275 ms 17696 KB Output isn't correct
80 Incorrect 174 ms 13016 KB Output isn't correct
81 Incorrect 160 ms 12824 KB Output isn't correct
82 Incorrect 225 ms 13208 KB Output isn't correct
83 Correct 270 ms 12736 KB Output is correct
84 Incorrect 273 ms 17236 KB Output isn't correct
85 Incorrect 232 ms 12848 KB Output isn't correct
86 Incorrect 243 ms 12788 KB Output isn't correct
87 Incorrect 284 ms 13152 KB Output isn't correct
88 Correct 244 ms 12768 KB Output is correct
89 Incorrect 239 ms 17840 KB Output isn't correct
90 Incorrect 308 ms 12952 KB Output isn't correct
91 Incorrect 319 ms 13660 KB Output isn't correct
92 Incorrect 278 ms 12704 KB Output isn't correct