oj.uz

Submission #834919

# Submission time Handle Problem Language Result Execution time Memory
834919 2023-08-23T01:34:10 Z NoLove Mecho (IOI09_mecho) C++14
26 / 100
 86 ms 9952 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 (g[x.i][x.j] == 'D') {
                cout << x.k;
                return 0;
            }
            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});
            }
        }
    }
    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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5332 KB Output isn't correct
2 Incorrect 2 ms 5332 KB Output isn't correct
3 Incorrect 3 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 2 ms 5332 KB Output is correct
7 Incorrect 68 ms 7884 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 3 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 3 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 3 ms 5460 KB Output is correct
25 Incorrect 2 ms 5332 KB Output isn't correct
26 Correct 2 ms 5460 KB Output is correct
27 Incorrect 2 ms 5460 KB Output isn't correct
28 Correct 2 ms 5460 KB Output is correct
29 Incorrect 2 ms 5460 KB Output isn't correct
30 Correct 4 ms 5460 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 8 ms 5588 KB Output isn't correct
34 Correct 8 ms 5588 KB Output is correct
35 Incorrect 12 ms 5972 KB Output isn't correct
36 Incorrect 8 ms 5732 KB Output isn't correct
37 Correct 8 ms 5716 KB Output is correct
38 Incorrect 15 ms 6036 KB Output isn't correct
39 Incorrect 9 ms 5716 KB Output isn't correct
40 Correct 9 ms 5716 KB Output is correct
41 Incorrect 19 ms 6100 KB Output isn't correct
42 Incorrect 11 ms 5716 KB Output isn't correct
43 Correct 11 ms 5716 KB Output is correct
44 Incorrect 22 ms 6228 KB Output isn't correct
45 Incorrect 13 ms 5844 KB Output isn't correct
46 Correct 13 ms 5844 KB Output is correct
47 Incorrect 25 ms 6256 KB Output isn't correct
48 Incorrect 14 ms 5872 KB Output isn't correct
49 Correct 14 ms 5884 KB Output is correct
50 Incorrect 31 ms 6348 KB Output isn't correct
51 Incorrect 20 ms 5844 KB Output isn't correct
52 Correct 17 ms 5844 KB Output is correct
53 Incorrect 35 ms 6456 KB Output isn't correct
54 Incorrect 19 ms 5844 KB Output isn't correct
55 Correct 19 ms 5844 KB Output is correct
56 Incorrect 52 ms 6504 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 6604 KB Output isn't correct
60 Incorrect 24 ms 6096 KB Output isn't correct
61 Correct 24 ms 5972 KB Output is correct
62 Incorrect 54 ms 6732 KB Output isn't correct
63 Correct 57 ms 6604 KB Output is correct
64 Correct 61 ms 6728 KB Output is correct
65 Correct 60 ms 6604 KB Output is correct
66 Incorrect 55 ms 6604 KB Output isn't correct
67 Correct 49 ms 6700 KB Output is correct
68 Correct 43 ms 6988 KB Output is correct
69 Correct 45 ms 6988 KB Output is correct
70 Correct 42 ms 6900 KB Output is correct
71 Correct 41 ms 6988 KB Output is correct
72 Incorrect 38 ms 6604 KB Output isn't correct
73 Incorrect 62 ms 9504 KB Output isn't correct
74 Correct 73 ms 9748 KB Output is correct
75 Correct 63 ms 9332 KB Output is correct
76 Correct 59 ms 9864 KB Output is correct
77 Correct 64 ms 9952 KB Output is correct
78 Correct 64 ms 9292 KB Output is correct
79 Incorrect 75 ms 9400 KB Output isn't correct
80 Incorrect 62 ms 9292 KB Output isn't correct
81 Incorrect 73 ms 9292 KB Output isn't correct
82 Incorrect 63 ms 9252 KB Output isn't correct
83 Correct 66 ms 8728 KB Output is correct
84 Incorrect 78 ms 9116 KB Output isn't correct
85 Incorrect 65 ms 8724 KB Output isn't correct
86 Incorrect 64 ms 8780 KB Output isn't correct
87 Incorrect 64 ms 8744 KB Output isn't correct
88 Correct 64 ms 8276 KB Output is correct
89 Incorrect 77 ms 8512 KB Output isn't correct
90 Incorrect 65 ms 8456 KB Output isn't correct
91 Incorrect 86 ms 8524 KB Output isn't correct
92 Incorrect 66 ms 8268 KB Output isn't correct