oj.uz

답안 #834916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834916 2023-08-23T01:18:54 Z NoLove Mecho (IOI09_mecho) C++14
26 / 100
 91 ms 9844 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;
    }
};

bool vaild1(int i, int j, int d) {
    return 0 <= i && i < n && 0 <= j && j < n &&
           d < dist[i][j] && g[i][j] != 'T' && g[i][j] != 'D';
}
bool vaild2(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 (vaild1(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});
            }
        }
    }

    while (q2.size()) {
        Data x = q2.front(); q2.pop();
        if (vaild2(x.i, x.j, x.t()) && x.k >= 0) {
            vis[x.i][x.j] = true;
            if (x.cnt % s == 0 && x.t() == dist[x.i][x.j]) continue;
            x.k = min(x.k, dist[x.i][x.j] - x.t() - (x.cnt % s != 0));
            db(x.i, x.j, x.k, x.t(), x.cnt, dist[x.i][x.j])
            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:62:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         auto[p, d] = q.front(); q.pop();
      |             ^
mecho.cpp:63:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         auto[i, j] = p;
      |             ^
mecho.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
26.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5288 KB Output isn't correct
2 Incorrect 2 ms 5332 KB Output isn't correct
3 Incorrect 2 ms 5332 KB Output isn't correct
4 Incorrect 2 ms 5332 KB Output isn't correct
5 Correct 2 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Incorrect 69 ms 7852 KB Output isn't correct
8 Correct 2 ms 5328 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 Correct 2 ms 5460 KB Output is correct
14 Correct 2 ms 5460 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 5332 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 2 ms 5332 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 3 ms 5460 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 5476 KB Output is correct
31 Incorrect 2 ms 5460 KB Output isn't correct
32 Correct 2 ms 5460 KB Output is correct
33 Incorrect 6 ms 5692 KB Output isn't correct
34 Correct 7 ms 5680 KB Output is correct
35 Incorrect 13 ms 5988 KB Output isn't correct
36 Incorrect 8 ms 5716 KB Output isn't correct
37 Correct 8 ms 5716 KB Output is correct
38 Incorrect 15 ms 6100 KB Output isn't correct
39 Incorrect 9 ms 5760 KB Output isn't correct
40 Correct 9 ms 5716 KB Output is correct
41 Incorrect 20 ms 6072 KB Output isn't correct
42 Incorrect 11 ms 5808 KB Output isn't correct
43 Correct 11 ms 5804 KB Output is correct
44 Incorrect 23 ms 6228 KB Output isn't correct
45 Incorrect 14 ms 5844 KB Output isn't correct
46 Correct 13 ms 5844 KB Output is correct
47 Incorrect 26 ms 6356 KB Output isn't correct
48 Incorrect 14 ms 5844 KB Output isn't correct
49 Correct 15 ms 5884 KB Output is correct
50 Incorrect 31 ms 6444 KB Output isn't correct
51 Incorrect 17 ms 5844 KB Output isn't correct
52 Correct 17 ms 5920 KB Output is correct
53 Incorrect 36 ms 6484 KB Output isn't correct
54 Incorrect 19 ms 5960 KB Output isn't correct
55 Correct 19 ms 5960 KB Output is correct
56 Incorrect 42 ms 6544 KB Output isn't correct
57 Incorrect 21 ms 5972 KB Output isn't correct
58 Correct 22 ms 5972 KB Output is correct
59 Incorrect 48 ms 6676 KB Output isn't correct
60 Incorrect 24 ms 5972 KB Output isn't correct
61 Correct 24 ms 5972 KB Output is correct
62 Incorrect 53 ms 6756 KB Output isn't correct
63 Correct 57 ms 6640 KB Output is correct
64 Correct 60 ms 6696 KB Output is correct
65 Correct 59 ms 6680 KB Output is correct
66 Incorrect 55 ms 6696 KB Output isn't correct
67 Correct 49 ms 6704 KB Output is correct
68 Correct 45 ms 6924 KB Output is correct
69 Correct 46 ms 6908 KB Output is correct
70 Correct 42 ms 6940 KB Output is correct
71 Correct 48 ms 6972 KB Output is correct
72 Incorrect 38 ms 6504 KB Output isn't correct
73 Incorrect 71 ms 9412 KB Output isn't correct
74 Correct 73 ms 9748 KB Output is correct
75 Correct 62 ms 9328 KB Output is correct
76 Correct 63 ms 9836 KB Output is correct
77 Correct 62 ms 9844 KB Output is correct
78 Correct 63 ms 9296 KB Output is correct
79 Incorrect 77 ms 9304 KB Output isn't correct
80 Incorrect 65 ms 9256 KB Output isn't correct
81 Incorrect 61 ms 9280 KB Output isn't correct
82 Incorrect 66 ms 9240 KB Output isn't correct
83 Correct 63 ms 8740 KB Output is correct
84 Incorrect 91 ms 9116 KB Output isn't correct
85 Incorrect 64 ms 8764 KB Output isn't correct
86 Incorrect 64 ms 8792 KB Output isn't correct
87 Incorrect 66 ms 8736 KB Output isn't correct
88 Correct 64 ms 8212 KB Output is correct
89 Incorrect 78 ms 8400 KB Output isn't correct
90 Incorrect 66 ms 8460 KB Output isn't correct
91 Incorrect 76 ms 8528 KB Output isn't correct
92 Incorrect 65 ms 8268 KB Output isn't correct