oj.uz

Submission #608650

# Submission time Handle Problem Language Result Execution time Memory
608650 2022-07-27T08:49:15 Z Mazaalai Mecho (IOI09_mecho) C++17
42 / 100
 192 ms 5740 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define LINE "---------------\n"
#define sz(a) (int)a.size()
using namespace std;
using PII = pair <int, int>;
const int N = 801;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, m, X1, Y1, X2, Y2;
    vector <PII> hives;
int mat[N][N], maze[N][N];
bool check(int lim) {
    memcpy(maze, mat, sizeof(mat));
    queue <PII> bfs1, bfs2;
    for (auto& [a, b] : hives) bfs2.push({a, b});
    // for (int i = 1; i <= n; i++)
    // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n];
    for (int i = 0; i < lim; i++) {
        int rep = sz(bfs2);
        for (int j = 0; j < rep; j++) {
            int x, y; tie(x, y) = bfs2.front(); bfs2.pop();
            for (int a = 0; a < 4; a++) {
                int xx = dx[a] + x;
                int yy = dy[a] + y;
                if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] == 1) continue;
                maze[xx][yy] = 1;
                bfs2.push({xx, yy});
            }
        }
    }
    // cout << LINE;
    // for (int i = 1; i <= n; i++)
    // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n];

    while (maze[X2][Y2] == 0) {
        // move bear
        mat[X1][Y1] = 2;
        bfs1.push({X1, Y1});
        for (int i = 0; i < m; i++) {
            int rep = sz(bfs1);
            for (int j = 0; j < rep; j++) {
                int x, y; tie(x, y) = bfs1.front(); bfs1.pop();
                if (maze[x][y] == 1) continue;
                for (int a = 0; a < 4; a++) {
                    int xx = dx[a] + x;
                    int yy = dy[a] + y;
                    if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] != 0) continue;
                    maze[xx][yy] = 2;
                    bfs1.push({xx, yy});
                }
            }
        }
        // cout << LINE;
        // cout << LINE;
        // for (int i = 1; i <= n; i++)
        // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n];
            
        if (maze[X2][Y2] != 0) return 1;
        // spread bees
        int rep = sz(bfs2);
        for (int j = 0; j < rep; j++) {
            int x, y; tie(x, y) = bfs2.front(); bfs2.pop();
            for (int a = 0; a < 4; a++) {
                int xx = dx[a] + x;
                int yy = dy[a] + y;
                if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] == 1) continue;
                maze[xx][yy] = 1;
                bfs2.push({xx, yy});
            }
        }

        // cout << LINE;
        // for (int i = 1; i <= n; i++)
        // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n];
            
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        char x; cin >> x;
        if (x == 'T') { // tree
            mat[i][j] = 1;
        } else if (x == 'G') { // grass
            mat[i][j] = 0;
        } else if (x == 'M') { // mecho the bear
            tie(X1, Y1) = mp(i, j);
            mat[i][j] = 0;
        } else if (x == 'D') { // home of the mecho
            mat[i][j] = 0;
            tie(X2, Y2) = mp(i, j);
        } else if (x == 'H') { // bee hive
            mat[i][j] = 1;
            hives.pb({i, j});
        }
    }
    int l = 0, r = 2*n, ans = -1;
    while (l <= r) {
        int m = (l+r)>>1;
        if (check(m)) {
            l = m+1;
            ans = m;
        } else {
            r = m-1;
        }
    }
    cout << ans << "\n";
}

Subtask #1
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Correct 2 ms 2772 KB Output is correct
4 Incorrect 2 ms 2772 KB Output isn't correct
5 Correct 2 ms 2772 KB Output is correct
6 Incorrect 2 ms 2772 KB Output isn't correct
7 Incorrect 114 ms 5400 KB Output isn't correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Incorrect 2 ms 2900 KB Output isn't correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct
15 Incorrect 2 ms 2900 KB Output isn't correct
16 Incorrect 2 ms 2900 KB Output isn't correct
17 Incorrect 2 ms 2900 KB Output isn't correct
18 Incorrect 2 ms 2900 KB Output isn't correct
19 Incorrect 2 ms 2900 KB Output isn't correct
20 Incorrect 2 ms 2900 KB Output isn't correct
21 Incorrect 2 ms 2900 KB Output isn't correct
22 Incorrect 3 ms 2900 KB Output isn't correct
23 Incorrect 2 ms 2900 KB Output isn't correct
24 Incorrect 3 ms 2900 KB Output isn't correct
25 Incorrect 3 ms 3028 KB Output isn't correct
26 Incorrect 2 ms 3028 KB Output isn't correct
27 Incorrect 3 ms 3028 KB Output isn't correct
28 Incorrect 2 ms 3028 KB Output isn't correct
29 Incorrect 2 ms 3028 KB Output isn't correct
30 Incorrect 2 ms 3028 KB Output isn't correct
31 Incorrect 2 ms 3028 KB Output isn't correct
32 Incorrect 3 ms 3028 KB Output isn't correct
33 Incorrect 4 ms 3924 KB Output isn't correct
34 Incorrect 5 ms 3940 KB Output isn't correct
35 Correct 10 ms 3944 KB Output is correct
36 Incorrect 5 ms 4052 KB Output isn't correct
37 Incorrect 5 ms 4052 KB Output isn't correct
38 Correct 19 ms 4052 KB Output is correct
39 Incorrect 5 ms 4168 KB Output isn't correct
40 Incorrect 6 ms 4252 KB Output isn't correct
41 Correct 18 ms 4260 KB Output is correct
42 Incorrect 5 ms 4308 KB Output isn't correct
43 Incorrect 7 ms 4404 KB Output isn't correct
44 Correct 23 ms 4416 KB Output is correct
45 Incorrect 7 ms 4484 KB Output isn't correct
46 Incorrect 7 ms 4564 KB Output isn't correct
47 Correct 26 ms 4468 KB Output is correct
48 Incorrect 7 ms 4692 KB Output isn't correct
49 Incorrect 7 ms 4692 KB Output isn't correct
50 Correct 29 ms 4688 KB Output is correct
51 Incorrect 8 ms 4820 KB Output isn't correct
52 Incorrect 9 ms 4820 KB Output isn't correct
53 Correct 33 ms 4940 KB Output is correct
54 Incorrect 9 ms 4948 KB Output isn't correct
55 Incorrect 10 ms 4916 KB Output isn't correct
56 Correct 37 ms 4948 KB Output is correct
57 Incorrect 9 ms 5076 KB Output isn't correct
58 Incorrect 12 ms 5072 KB Output isn't correct
59 Correct 41 ms 5184 KB Output is correct
60 Incorrect 11 ms 5336 KB Output isn't correct
61 Incorrect 11 ms 5332 KB Output isn't correct
62 Correct 56 ms 5328 KB Output is correct
63 Correct 184 ms 5332 KB Output is correct
64 Correct 192 ms 5452 KB Output is correct
65 Correct 165 ms 5332 KB Output is correct
66 Correct 160 ms 5332 KB Output is correct
67 Correct 168 ms 5336 KB Output is correct
68 Correct 145 ms 5360 KB Output is correct
69 Correct 127 ms 5360 KB Output is correct
70 Correct 151 ms 5332 KB Output is correct
71 Correct 154 ms 5364 KB Output is correct
72 Correct 161 ms 5364 KB Output is correct
73 Correct 144 ms 5740 KB Output is correct
74 Correct 147 ms 5640 KB Output is correct
75 Correct 144 ms 5640 KB Output is correct
76 Correct 158 ms 5644 KB Output is correct
77 Correct 138 ms 5632 KB Output is correct
78 Correct 128 ms 5604 KB Output is correct
79 Correct 160 ms 5592 KB Output is correct
80 Correct 140 ms 5596 KB Output is correct
81 Correct 152 ms 5528 KB Output is correct
82 Correct 150 ms 5504 KB Output is correct
83 Correct 150 ms 5564 KB Output is correct
84 Correct 144 ms 5552 KB Output is correct
85 Correct 148 ms 5560 KB Output is correct
86 Correct 151 ms 5700 KB Output is correct
87 Correct 150 ms 5556 KB Output is correct
88 Correct 147 ms 5500 KB Output is correct
89 Correct 150 ms 5516 KB Output is correct
90 Correct 157 ms 5500 KB Output is correct
91 Correct 165 ms 5496 KB Output is correct
92 Correct 146 ms 5504 KB Output is correct