oj.uz

Submission #608780

# Submission time Handle Problem Language Result Execution time Memory
608780 2022-07-27T10:04:08 Z Mazaalai Mecho (IOI09_mecho) C++17
6 / 100
 1000 ms 5660 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 = 802;
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) {
    // cout << "START: " << lim << '\n';
    memcpy(maze, mat, sizeof(mat));
    queue <PII> bfs1, bfs2;
    for (auto& [a, b] : hives) bfs2.push({a, b});
    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 || mp(xx, yy) == mp(X2, Y2)) continue;
                maze[xx][yy] = 1;
                bfs2.push({xx, yy});
            }
        }
    }
    maze[X1][Y1] = 2;
    // 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[X1][Y1] == 1) return 0;
    bfs1.push({X1, Y1});
    while (maze[X2][Y2] == 0) {
        // move bear
        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] == 2) 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 || mp(xx, yy) == mp(X2, Y2)) 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 = 1, 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
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Incorrect 2 ms 2772 KB Output isn't correct
4 Incorrect 3 ms 2748 KB Output isn't correct
5 Execution timed out 1078 ms 2772 KB Time limit exceeded
6 Correct 4 ms 2772 KB Output is correct
7 Incorrect 41 ms 5460 KB Output isn't correct
8 Execution timed out 1072 ms 2772 KB Time limit exceeded
9 Incorrect 3 ms 2816 KB Output isn't correct
10 Incorrect 2 ms 2772 KB Output isn't correct
11 Incorrect 3 ms 2772 KB Output isn't correct
12 Incorrect 3 ms 3028 KB Output isn't correct
13 Incorrect 2 ms 2900 KB Output isn't correct
14 Execution timed out 1085 ms 3028 KB Time limit exceeded
15 Incorrect 2 ms 2900 KB Output isn't correct
16 Incorrect 2 ms 2900 KB Output isn't correct
17 Incorrect 3 ms 2900 KB Output isn't correct
18 Incorrect 2 ms 2900 KB Output isn't correct
19 Incorrect 4 ms 2900 KB Output isn't correct
20 Incorrect 4 ms 2900 KB Output isn't correct
21 Incorrect 4 ms 2900 KB Output isn't correct
22 Incorrect 2 ms 2900 KB Output isn't correct
23 Incorrect 2 ms 2900 KB Output isn't correct
24 Incorrect 2 ms 2900 KB Output isn't correct
25 Incorrect 5 ms 3028 KB Output isn't correct
26 Incorrect 2 ms 3028 KB Output isn't correct
27 Incorrect 2 ms 3028 KB Output isn't correct
28 Incorrect 4 ms 3028 KB Output isn't correct
29 Incorrect 4 ms 3028 KB Output isn't correct
30 Incorrect 5 ms 3028 KB Output isn't correct
31 Incorrect 2 ms 3028 KB Output isn't correct
32 Incorrect 4 ms 3028 KB Output isn't correct
33 Incorrect 4 ms 3924 KB Output isn't correct
34 Incorrect 4 ms 3924 KB Output isn't correct
35 Incorrect 6 ms 3924 KB Output isn't correct
36 Incorrect 10 ms 4016 KB Output isn't correct
37 Incorrect 4 ms 4052 KB Output isn't correct
38 Incorrect 8 ms 4052 KB Output isn't correct
39 Incorrect 5 ms 4220 KB Output isn't correct
40 Incorrect 5 ms 4180 KB Output isn't correct
41 Incorrect 9 ms 4180 KB Output isn't correct
42 Incorrect 9 ms 4308 KB Output isn't correct
43 Incorrect 5 ms 4392 KB Output isn't correct
44 Incorrect 13 ms 4408 KB Output isn't correct
45 Incorrect 6 ms 4564 KB Output isn't correct
46 Incorrect 6 ms 4564 KB Output isn't correct
47 Incorrect 12 ms 4564 KB Output isn't correct
48 Incorrect 15 ms 4692 KB Output isn't correct
49 Incorrect 7 ms 4692 KB Output isn't correct
50 Incorrect 17 ms 4736 KB Output isn't correct
51 Incorrect 7 ms 4844 KB Output isn't correct
52 Incorrect 7 ms 4820 KB Output isn't correct
53 Incorrect 20 ms 4824 KB Output isn't correct
54 Incorrect 8 ms 4948 KB Output isn't correct
55 Incorrect 9 ms 4956 KB Output isn't correct
56 Incorrect 23 ms 4960 KB Output isn't correct
57 Incorrect 11 ms 5076 KB Output isn't correct
58 Incorrect 9 ms 5084 KB Output isn't correct
59 Incorrect 21 ms 5204 KB Output isn't correct
60 Incorrect 10 ms 5304 KB Output isn't correct
61 Incorrect 11 ms 5324 KB Output isn't correct
62 Incorrect 25 ms 5344 KB Output isn't correct
63 Execution timed out 1092 ms 5312 KB Time limit exceeded
64 Incorrect 36 ms 5332 KB Output isn't correct
65 Incorrect 38 ms 5332 KB Output isn't correct
66 Incorrect 39 ms 5332 KB Output isn't correct
67 Execution timed out 1089 ms 5264 KB Time limit exceeded
68 Execution timed out 1086 ms 5332 KB Time limit exceeded
69 Incorrect 31 ms 5360 KB Output isn't correct
70 Incorrect 55 ms 5332 KB Output isn't correct
71 Incorrect 41 ms 5372 KB Output isn't correct
72 Incorrect 15 ms 5268 KB Output isn't correct
73 Correct 36 ms 5588 KB Output is correct
74 Incorrect 29 ms 5460 KB Output isn't correct
75 Incorrect 36 ms 5588 KB Output isn't correct
76 Incorrect 37 ms 5660 KB Output isn't correct
77 Incorrect 35 ms 5640 KB Output isn't correct
78 Execution timed out 1088 ms 5588 KB Time limit exceeded
79 Incorrect 41 ms 5488 KB Output isn't correct
80 Incorrect 55 ms 5612 KB Output isn't correct
81 Incorrect 56 ms 5616 KB Output isn't correct
82 Incorrect 56 ms 5608 KB Output isn't correct
83 Execution timed out 1078 ms 5460 KB Time limit exceeded
84 Incorrect 38 ms 5456 KB Output isn't correct
85 Incorrect 41 ms 5560 KB Output isn't correct
86 Incorrect 38 ms 5572 KB Output isn't correct
87 Incorrect 38 ms 5536 KB Output isn't correct
88 Execution timed out 1058 ms 5460 KB Time limit exceeded
89 Incorrect 44 ms 5404 KB Output isn't correct
90 Incorrect 63 ms 5516 KB Output isn't correct
91 Incorrect 47 ms 5512 KB Output isn't correct
92 Incorrect 52 ms 5516 KB Output isn't correct