oj.uz

Submission #834921

# Submission time Handle Problem Language Result Execution time Memory
834921 2023-08-23T01:54:08 Z NoLove Mecho (IOI09_mecho) C++14
57 / 100
 84 ms 9932 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 in_gird(int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < n && 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 (in_gird(i, j)) {
            if (g[i][j] == 'D' or dist[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 (in_gird(x.i, x.j) && x.k >= 0) {
            if (vis[x.i][x.j]) continue;
            vis[x.i][x.j] = true;
            if (g[x.i][x.j] == 'D') {
                cout << x.k;
                return 0;
            }
            if (x.cnt >= dist[x.i][x.j]*s) continue;
            x.k = min(x.k, (dist[x.i][x.j]*s - x.cnt) / s - ((dist[x.i][x.j]*s - 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:57:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         auto[p, d] = q.front(); q.pop();
      |             ^
mecho.cpp:58:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         auto[i, j] = p;
      |             ^
mecho.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5332 KB Output is correct
2 Correct 2 ms 5332 KB Output is correct
3 Correct 2 ms 5332 KB Output is correct
4 Correct 2 ms 5332 KB Output is correct
5 Correct 2 ms 5332 KB Output is correct
6 Correct 2 ms 5332 KB Output is correct
7 Incorrect 70 ms 7844 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 Correct 2 ms 5460 KB Output is correct
13 Correct 2 ms 5460 KB Output is correct
14 Correct 2 ms 5460 KB Output is correct
15 Correct 2 ms 5356 KB Output is correct
16 Correct 2 ms 5332 KB Output is correct
17 Correct 2 ms 5332 KB Output is correct
18 Correct 2 ms 5328 KB Output is correct
19 Correct 2 ms 5332 KB Output is correct
20 Correct 2 ms 5332 KB Output is correct
21 Correct 2 ms 5332 KB Output is correct
22 Correct 2 ms 5332 KB Output is correct
23 Correct 2 ms 5332 KB Output is correct
24 Correct 2 ms 5460 KB Output is correct
25 Correct 2 ms 5460 KB Output is correct
26 Correct 2 ms 5460 KB Output is correct
27 Correct 3 ms 5460 KB Output is correct
28 Correct 2 ms 5460 KB Output is correct
29 Correct 2 ms 5460 KB Output is correct
30 Correct 2 ms 5460 KB Output is correct
31 Correct 2 ms 5460 KB Output is correct
32 Correct 3 ms 5460 KB Output is correct
33 Correct 6 ms 5640 KB Output is correct
34 Correct 6 ms 5588 KB Output is correct
35 Incorrect 15 ms 5984 KB Output isn't correct
36 Correct 9 ms 5728 KB Output is correct
37 Correct 8 ms 5696 KB Output is correct
38 Incorrect 15 ms 6096 KB Output isn't correct
39 Correct 9 ms 5764 KB Output is correct
40 Correct 9 ms 5760 KB Output is correct
41 Incorrect 17 ms 6100 KB Output isn't correct
42 Correct 11 ms 5804 KB Output is correct
43 Correct 10 ms 5804 KB Output is correct
44 Incorrect 21 ms 6164 KB Output isn't correct
45 Correct 12 ms 5840 KB Output is correct
46 Correct 12 ms 5840 KB Output is correct
47 Incorrect 25 ms 6356 KB Output isn't correct
48 Correct 14 ms 5828 KB Output is correct
49 Correct 14 ms 5844 KB Output is correct
50 Incorrect 29 ms 6344 KB Output isn't correct
51 Correct 16 ms 5844 KB Output is correct
52 Correct 16 ms 5924 KB Output is correct
53 Incorrect 34 ms 6408 KB Output isn't correct
54 Correct 18 ms 5968 KB Output is correct
55 Correct 18 ms 5956 KB Output is correct
56 Incorrect 39 ms 6564 KB Output isn't correct
57 Correct 22 ms 5996 KB Output is correct
58 Correct 20 ms 6000 KB Output is correct
59 Incorrect 45 ms 6604 KB Output isn't correct
60 Correct 23 ms 5972 KB Output is correct
61 Correct 23 ms 6016 KB Output is correct
62 Incorrect 53 ms 6756 KB Output isn't correct
63 Correct 57 ms 6684 KB Output is correct
64 Correct 64 ms 6604 KB Output is correct
65 Correct 60 ms 6704 KB Output is correct
66 Correct 62 ms 6576 KB Output is correct
67 Correct 49 ms 6688 KB Output is correct
68 Correct 53 ms 6988 KB Output is correct
69 Correct 47 ms 6900 KB Output is correct
70 Correct 44 ms 6904 KB Output is correct
71 Correct 41 ms 6892 KB Output is correct
72 Correct 38 ms 6520 KB Output is correct
73 Correct 58 ms 9516 KB Output is correct
74 Correct 75 ms 9660 KB Output is correct
75 Correct 57 ms 9328 KB Output is correct
76 Correct 61 ms 9892 KB Output is correct
77 Correct 59 ms 9932 KB Output is correct
78 Correct 61 ms 9256 KB Output is correct
79 Incorrect 70 ms 9352 KB Output isn't correct
80 Incorrect 59 ms 9256 KB Output isn't correct
81 Incorrect 57 ms 9268 KB Output isn't correct
82 Incorrect 63 ms 9248 KB Output isn't correct
83 Correct 59 ms 8744 KB Output is correct
84 Incorrect 72 ms 8992 KB Output isn't correct
85 Incorrect 59 ms 8724 KB Output isn't correct
86 Incorrect 62 ms 8748 KB Output isn't correct
87 Incorrect 62 ms 8724 KB Output isn't correct
88 Correct 59 ms 8216 KB Output is correct
89 Incorrect 84 ms 8428 KB Output isn't correct
90 Incorrect 61 ms 8456 KB Output isn't correct
91 Incorrect 67 ms 8560 KB Output isn't correct
92 Incorrect 61 ms 8320 KB Output isn't correct