oj.uz

Submission #834920

# Submission time Handle Problem Language Result Execution time Memory
834920 2023-08-23T01:50:41 Z NoLove Mecho (IOI09_mecho) C++14
26 / 100
 72 ms 9848 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);
            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
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 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 2 ms 5332 KB Output is correct
7 Incorrect 66 ms 7848 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 5332 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 2 ms 5460 KB Output is correct
25 Incorrect 2 ms 5460 KB Output isn't correct
26 Correct 3 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 3 ms 5460 KB Output is correct
31 Incorrect 3 ms 5460 KB Output isn't correct
32 Correct 2 ms 5460 KB Output is correct
33 Incorrect 7 ms 5588 KB Output isn't correct
34 Correct 9 ms 5696 KB Output is correct
35 Incorrect 11 ms 5972 KB Output isn't correct
36 Incorrect 8 ms 5724 KB Output isn't correct
37 Correct 7 ms 5716 KB Output is correct
38 Incorrect 14 ms 6100 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 18 ms 6100 KB Output isn't correct
42 Incorrect 10 ms 5808 KB Output isn't correct
43 Correct 10 ms 5716 KB Output is correct
44 Incorrect 21 ms 6204 KB Output isn't correct
45 Incorrect 12 ms 5844 KB Output isn't correct
46 Correct 12 ms 5844 KB Output is correct
47 Incorrect 24 ms 6356 KB Output isn't correct
48 Incorrect 13 ms 5884 KB Output isn't correct
49 Correct 14 ms 5844 KB Output is correct
50 Incorrect 29 ms 6444 KB Output isn't correct
51 Incorrect 16 ms 5924 KB Output isn't correct
52 Correct 16 ms 5844 KB Output is correct
53 Incorrect 34 ms 6484 KB Output isn't correct
54 Incorrect 18 ms 5844 KB Output isn't correct
55 Correct 18 ms 5964 KB Output is correct
56 Incorrect 46 ms 6640 KB Output isn't correct
57 Incorrect 20 ms 6004 KB Output isn't correct
58 Correct 20 ms 5972 KB Output is correct
59 Incorrect 44 ms 6604 KB Output isn't correct
60 Incorrect 25 ms 5924 KB Output isn't correct
61 Correct 23 ms 5972 KB Output is correct
62 Incorrect 50 ms 6732 KB Output isn't correct
63 Correct 58 ms 6692 KB Output is correct
64 Correct 67 ms 6712 KB Output is correct
65 Correct 64 ms 6724 KB Output is correct
66 Incorrect 55 ms 6568 KB Output isn't correct
67 Correct 49 ms 6712 KB Output is correct
68 Correct 43 ms 6904 KB Output is correct
69 Correct 46 ms 6896 KB Output is correct
70 Correct 42 ms 6888 KB Output is correct
71 Correct 43 ms 6904 KB Output is correct
72 Incorrect 40 ms 6540 KB Output isn't correct
73 Incorrect 60 ms 9516 KB Output isn't correct
74 Correct 68 ms 9656 KB Output is correct
75 Correct 56 ms 9420 KB Output is correct
76 Correct 55 ms 9780 KB Output is correct
77 Correct 59 ms 9848 KB Output is correct
78 Correct 62 ms 9264 KB Output is correct
79 Incorrect 71 ms 9296 KB Output isn't correct
80 Incorrect 62 ms 9268 KB Output isn't correct
81 Incorrect 62 ms 9260 KB Output isn't correct
82 Incorrect 60 ms 9276 KB Output isn't correct
83 Correct 63 ms 8736 KB Output is correct
84 Incorrect 70 ms 9080 KB Output isn't correct
85 Incorrect 59 ms 8732 KB Output isn't correct
86 Incorrect 58 ms 8796 KB Output isn't correct
87 Incorrect 72 ms 8728 KB Output isn't correct
88 Correct 60 ms 8228 KB Output is correct
89 Incorrect 71 ms 8508 KB Output isn't correct
90 Incorrect 63 ms 8456 KB Output isn't correct
91 Incorrect 68 ms 8512 KB Output isn't correct
92 Incorrect 72 ms 8204 KB Output isn't correct