oj.uz

답안 #550463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
550463 2022-04-18T08:59:15 Z Jomnoi Mecho (IOI09_mecho) C++17
3 / 100
 146 ms 6936 KB 
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int MAX_N = 810;
const int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

char s[MAX_N][MAX_N];
int db[MAX_N][MAX_N], dm[MAX_N][MAX_N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, S;
    cin >> N >> S;
    S++;
    for(int i = 1; i <= N; i++) {
        cin >> (s[i] + 1);
    }

    int sx, sy, ex, ey;
    queue <pair <int, int>> q;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            db[i][j] = -1;
            if(s[i][j] == 'H') {
                db[i][j] = 0;
                q.emplace(i, j);
            }
            else if(s[i][j] == 'M') {
                sx = i, sy = j;
            }
            else if(s[i][j] == 'D') {
                ex = i, ey = j;
            }
        }    
    }

    while(!q.empty()) {
        auto [ux, uy] = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            int vx = ux + d[i][0], vy = uy + d[i][1];
            if(vx < 1 or vx > N or vy < 1 or vy > N or s[vx][vy] == 'T' or s[vx][vy] == 'D' or db[vx][vy] != -1) {
                continue;
            }

            db[vx][vy] = db[ux][uy] + 1;
            q.emplace(vx, vy);
        }
    }

    int l = 0, r = 100, ans = -1;
    while(l <= r) {
        int mid = (l + r) / 2;

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                dm[i][j] = -1;
            }
        }

        queue <pair <int, int>> q;
        q.emplace(sx, sy);
        dm[sx][sy] = mid * S;
        while(!q.empty()) {
            auto [ux, uy] = q.front();
            q.pop();

            for(int i = 0; i < 4; i++) {
                int vx = ux + d[i][0], vy = uy + d[i][1];
                if(vx < 1 or vx > N or vy < 1 or vy > N or s[vx][vy] == 'T' or dm[vx][vy] != -1) {
                    continue;
                }
                if(db[vx][vy] != -1 and (dm[ux][uy] + 1) / S >= db[vx][vy]) {
                    continue;
                }

                dm[vx][vy] = dm[ux][uy] + 1;
                q.emplace(vx, vy);
            }
        }

        if(dm[ex][ey] == -1) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
            ans = mid;
        }
    }
    cout << ans;
    return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:84:21: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         if(dm[ex][ey] == -1) {
      |            ~~~~~~~~~^
mecho.cpp:84:21: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
3.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 328 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 72 ms 6764 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Incorrect 1 ms 724 KB Output isn't correct
13 Incorrect 1 ms 596 KB Output isn't correct
14 Incorrect 1 ms 724 KB Output isn't correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Correct 1 ms 468 KB Output is correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Incorrect 1 ms 468 KB Output isn't correct
19 Incorrect 1 ms 468 KB Output isn't correct
20 Incorrect 1 ms 468 KB Output isn't correct
21 Incorrect 1 ms 596 KB Output isn't correct
22 Incorrect 1 ms 596 KB Output isn't correct
23 Incorrect 1 ms 584 KB Output isn't correct
24 Incorrect 1 ms 596 KB Output isn't correct
25 Incorrect 1 ms 724 KB Output isn't correct
26 Incorrect 1 ms 716 KB Output isn't correct
27 Incorrect 1 ms 716 KB Output isn't correct
28 Incorrect 1 ms 724 KB Output isn't correct
29 Incorrect 1 ms 724 KB Output isn't correct
30 Incorrect 1 ms 844 KB Output isn't correct
31 Incorrect 1 ms 852 KB Output isn't correct
32 Incorrect 1 ms 852 KB Output isn't correct
33 Incorrect 9 ms 2896 KB Output isn't correct
34 Incorrect 12 ms 2900 KB Output isn't correct
35 Correct 25 ms 2904 KB Output is correct
36 Incorrect 15 ms 3284 KB Output isn't correct
37 Incorrect 17 ms 3344 KB Output isn't correct
38 Correct 25 ms 3336 KB Output is correct
39 Incorrect 15 ms 3720 KB Output isn't correct
40 Incorrect 22 ms 3720 KB Output isn't correct
41 Correct 30 ms 3664 KB Output is correct
42 Incorrect 19 ms 4096 KB Output isn't correct
43 Incorrect 23 ms 4132 KB Output isn't correct
44 Correct 39 ms 4140 KB Output is correct
45 Incorrect 26 ms 4432 KB Output isn't correct
46 Incorrect 31 ms 4432 KB Output isn't correct
47 Correct 45 ms 4436 KB Output is correct
48 Incorrect 25 ms 4948 KB Output isn't correct
49 Incorrect 33 ms 4948 KB Output isn't correct
50 Correct 53 ms 4948 KB Output is correct
51 Incorrect 36 ms 5332 KB Output isn't correct
52 Incorrect 38 ms 5296 KB Output isn't correct
53 Correct 65 ms 5380 KB Output is correct
54 Incorrect 35 ms 5760 KB Output isn't correct
55 Incorrect 49 ms 5756 KB Output isn't correct
56 Correct 66 ms 5800 KB Output is correct
57 Incorrect 38 ms 6132 KB Output isn't correct
58 Incorrect 49 ms 6228 KB Output isn't correct
59 Correct 85 ms 6228 KB Output is correct
60 Incorrect 44 ms 6604 KB Output isn't correct
61 Incorrect 58 ms 6652 KB Output isn't correct
62 Correct 88 ms 6656 KB Output is correct
63 Incorrect 128 ms 6604 KB Output isn't correct
64 Incorrect 140 ms 6648 KB Output isn't correct
65 Incorrect 146 ms 6716 KB Output isn't correct
66 Incorrect 125 ms 6572 KB Output isn't correct
67 Incorrect 123 ms 6656 KB Output isn't correct
68 Incorrect 38 ms 6604 KB Output isn't correct
69 Correct 37 ms 6604 KB Output is correct
70 Incorrect 35 ms 6644 KB Output isn't correct
71 Incorrect 30 ms 6604 KB Output isn't correct
72 Incorrect 47 ms 6680 KB Output isn't correct
73 Incorrect 34 ms 6860 KB Output isn't correct
74 Incorrect 61 ms 6824 KB Output isn't correct
75 Incorrect 53 ms 6924 KB Output isn't correct
76 Incorrect 48 ms 6844 KB Output isn't correct
77 Incorrect 61 ms 6936 KB Output isn't correct
78 Incorrect 69 ms 6904 KB Output isn't correct
79 Incorrect 60 ms 6904 KB Output isn't correct
80 Incorrect 48 ms 6904 KB Output isn't correct
81 Incorrect 58 ms 6828 KB Output isn't correct
82 Incorrect 68 ms 6928 KB Output isn't correct
83 Incorrect 66 ms 6860 KB Output isn't correct
84 Correct 53 ms 6784 KB Output is correct
85 Incorrect 60 ms 6768 KB Output isn't correct
86 Incorrect 57 ms 6756 KB Output isn't correct
87 Correct 65 ms 6864 KB Output is correct
88 Incorrect 70 ms 6828 KB Output isn't correct
89 Correct 66 ms 6812 KB Output is correct
90 Correct 68 ms 6812 KB Output is correct
91 Correct 69 ms 6816 KB Output is correct
92 Incorrect 71 ms 6712 KB Output isn't correct