oj.uz

답안 #834908

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834908 2023-08-23T00:48:56 Z NoLove Mecho (IOI09_mecho) C++14
21 / 100
 80 ms 10500 KB 
/**
 *    author : Lăng Trọng Đạt
 *    created: 2023-08-22
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int int64_t
#define mp make_pair
#define pb push_back
using pii = pair<int, int>;

const int MAXN = 800 + 5;
int dist[MAXN][MAXN];
char g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int x_change[]{1, -1, 0, 0};
int y_change[]{0, 0, 1, -1};
int n, s;

struct Data {
    int i, j, cnt, k;
    // cnt: number of step, k: : the maximum possible number of minutes that Mecho can continue eating honey at his initial location, while still being able to get home safely.
    // @return number of minutes passed
    int t() {
        return cnt / s + (cnt % s != 0);
    }
};

bool vaild(int i, int j, int d) {
    return 0 <= i && i < n && 0 <= j && j < n &&
           !vis[i][j] && d < dist[i][j] && g[i][j] != 'T';
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    }

    cin >> n >> s;
    queue<pair<pii, int>> q;
    queue<Data> q2;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'H') {
                q.push({{i, j}, 0});
            } else if (g[i][j] == 'M') {
                q2.push({i, j, 0, n*n});
            }
        }
    memset(dist, 0x3f3f3f, sizeof(dist));
    while (q.size()) {
        auto[p, d] = q.front(); q.pop();
        auto[i, j] = p;
        if (vaild(i, j, d)) {
            if (g[i][j] == 'D') continue;
            dist[i][j] = d;
            for (int k = 0; k < 4; k++) {
                q.push({{i + x_change[k], j + y_change[k]}, d + 1});
            }
//            db(i, j, dist[i][j], g[i][j])
        }
    }

    while (q2.size()) {
        Data x = q2.front(); q2.pop();
        if (vaild(x.i, x.j, x.t()) && x.k >= 0) {
            vis[x.i][x.j] = true;
            x.k = min(x.k, dist[x.i][x.j] - x.t());
//            db(x.i, x.j, x.k)
            for (int k = 0; k < 4; k++) {
                q2.push({x.i + x_change[k], x.j + y_change[k], x.cnt + 1, x.k});
            }
            if (g[x.i][x.j] == 'D') {
                cout << x.k;
                return 0;
            }
        }
    }
    cout << -1;
}

Compilation message

mecho.cpp: In function 'int32_t main()':
mecho.cpp:58:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         auto[p, d] = q.front(); q.pop();
      |             ^
mecho.cpp:59:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         auto[i, j] = p;
      |             ^
mecho.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5332 KB Output isn't correct
2 Incorrect 2 ms 5316 KB Output isn't correct
3 Incorrect 2 ms 5332 KB Output isn't correct
4 Incorrect 2 ms 5364 KB Output isn't correct
5 Incorrect 2 ms 5332 KB Output isn't correct
6 Correct 2 ms 5332 KB Output is correct
7 Incorrect 69 ms 8524 KB Output isn't correct
8 Correct 2 ms 5332 KB Output is correct
9 Correct 2 ms 5332 KB Output is correct
10 Correct 2 ms 5332 KB Output is correct
11 Correct 2 ms 5332 KB Output is correct
12 Incorrect 2 ms 5460 KB Output isn't correct
13 Incorrect 2 ms 5460 KB Output isn't correct
14 Correct 3 ms 5448 KB Output is correct
15 Incorrect 2 ms 5332 KB Output isn't correct
16 Correct 2 ms 5332 KB Output is correct
17 Incorrect 2 ms 5332 KB Output isn't correct
18 Correct 2 ms 5332 KB Output is correct
19 Incorrect 2 ms 5320 KB Output isn't correct
20 Correct 2 ms 5332 KB Output is correct
21 Incorrect 2 ms 5332 KB Output isn't correct
22 Correct 2 ms 5332 KB Output is correct
23 Incorrect 3 ms 5444 KB Output isn't correct
24 Correct 2 ms 5460 KB Output is correct
25 Incorrect 2 ms 5460 KB Output isn't correct
26 Correct 2 ms 5460 KB Output is correct
27 Incorrect 2 ms 5448 KB Output isn't correct
28 Correct 2 ms 5460 KB Output is correct
29 Incorrect 3 ms 5460 KB Output isn't correct
30 Correct 2 ms 5460 KB Output is correct
31 Incorrect 2 ms 5448 KB Output isn't correct
32 Correct 2 ms 5460 KB Output is correct
33 Incorrect 6 ms 5716 KB Output isn't correct
34 Correct 7 ms 5808 KB Output is correct
35 Incorrect 12 ms 6100 KB Output isn't correct
36 Incorrect 8 ms 5840 KB Output isn't correct
37 Correct 8 ms 5844 KB Output is correct
38 Incorrect 15 ms 6148 KB Output isn't correct
39 Incorrect 9 ms 5836 KB Output isn't correct
40 Correct 10 ms 5968 KB Output is correct
41 Incorrect 18 ms 6280 KB Output isn't correct
42 Incorrect 11 ms 6052 KB Output isn't correct
43 Correct 11 ms 5972 KB Output is correct
44 Incorrect 25 ms 6484 KB Output isn't correct
45 Incorrect 13 ms 6100 KB Output isn't correct
46 Correct 13 ms 6104 KB Output is correct
47 Incorrect 26 ms 6612 KB Output isn't correct
48 Incorrect 15 ms 6132 KB Output isn't correct
49 Correct 15 ms 6212 KB Output is correct
50 Incorrect 31 ms 6704 KB Output isn't correct
51 Incorrect 17 ms 6228 KB Output isn't correct
52 Correct 18 ms 6336 KB Output is correct
53 Incorrect 36 ms 6808 KB Output isn't correct
54 Incorrect 20 ms 6444 KB Output isn't correct
55 Correct 20 ms 6448 KB Output is correct
56 Incorrect 42 ms 7028 KB Output isn't correct
57 Incorrect 22 ms 6536 KB Output isn't correct
58 Correct 22 ms 6480 KB Output is correct
59 Incorrect 47 ms 7152 KB Output isn't correct
60 Incorrect 25 ms 6612 KB Output isn't correct
61 Correct 24 ms 6568 KB Output is correct
62 Incorrect 53 ms 7360 KB Output isn't correct
63 Incorrect 46 ms 7316 KB Output isn't correct
64 Correct 61 ms 7212 KB Output is correct
65 Correct 65 ms 7372 KB Output is correct
66 Incorrect 55 ms 7248 KB Output isn't correct
67 Correct 53 ms 7328 KB Output is correct
68 Incorrect 43 ms 7568 KB Output isn't correct
69 Correct 46 ms 7524 KB Output is correct
70 Correct 44 ms 7628 KB Output is correct
71 Correct 43 ms 7532 KB Output is correct
72 Incorrect 37 ms 7116 KB Output isn't correct
73 Incorrect 62 ms 10040 KB Output isn't correct
74 Correct 73 ms 10304 KB Output is correct
75 Correct 61 ms 9956 KB Output is correct
76 Correct 61 ms 10500 KB Output is correct
77 Correct 62 ms 10484 KB Output is correct
78 Correct 65 ms 9884 KB Output is correct
79 Incorrect 80 ms 9932 KB Output isn't correct
80 Incorrect 67 ms 9868 KB Output isn't correct
81 Incorrect 65 ms 9848 KB Output isn't correct
82 Incorrect 64 ms 9876 KB Output isn't correct
83 Incorrect 64 ms 9356 KB Output isn't correct
84 Incorrect 77 ms 9624 KB Output isn't correct
85 Incorrect 65 ms 9364 KB Output isn't correct
86 Incorrect 72 ms 9556 KB Output isn't correct
87 Incorrect 73 ms 9356 KB Output isn't correct
88 Incorrect 65 ms 8832 KB Output isn't correct
89 Incorrect 79 ms 9028 KB Output isn't correct
90 Incorrect 68 ms 8908 KB Output isn't correct
91 Incorrect 72 ms 9200 KB Output isn't correct
92 Incorrect 64 ms 8936 KB Output isn't correct