oj.uz

Submission #978131

# Submission time Handle Problem Language Result Execution time Memory
978131 2024-05-08T21:52:30 Z Bodisha Mecho (IOI09_mecho) C++17
40 / 100
 174 ms 7860 KB 
#include <bits/stdc++.h>
#define MAX_N 801
#define UNVISITED 0
#define BEAR 1
#define BEE 2

using namespace std;

int n, s;
char grid[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
int beed[MAX_N][MAX_N];

bool check(int t) {
    pair<int, int> mecho_pos;
    pair<int, int> home_pos;
    vector<pair<int, int>> hive_edges;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = UNVISITED;
            beed[i][j] = -69;
            if(grid[i][j] == 'H') {
                hive_edges.push_back({i, j});
            }
            if(grid[i][j] == 'M') {
                mecho_pos = {i, j};
            }
            if(grid[i][j] == 'D') {
                home_pos = {i, j};
            }
        }
    }
    queue<pair<int, int>> beeq;
    vector<pair<int, int>> bees_edge;
    for(auto iter : hive_edges) {
        visited[iter.first][iter.second] = BEE;
        beed[iter.first][iter.second] = 0;
        beeq.push(iter);
    }
    while(!beeq.empty()) {
        pair<int, int> curr = beeq.front();
        beeq.pop();
        if(beed[curr.first][curr.second] == t) {
            bees_edge.push_back(curr);
            continue;
        }
        if(visited[curr.first + 1][curr.second] == UNVISITED && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) {
            visited[curr.first + 1][curr.second] = BEE;
            beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first + 1, curr.second});
        }
        if(visited[curr.first - 1][curr.second] == UNVISITED && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) {
            visited[curr.first - 1][curr.second] = BEE;
            beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first - 1, curr.second});
        }
        if(visited[curr.first][curr.second + 1] == UNVISITED && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) {
            visited[curr.first][curr.second + 1] = BEE;
            beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first, curr.second + 1});
        }
        if(visited[curr.first][curr.second - 1] == UNVISITED && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) {
            visited[curr.first][curr.second - 1] = BEE;
            beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first, curr.second - 1});
        }
    }
    if(visited[mecho_pos.first][mecho_pos.second] == BEE) {
        return false;
    }
    set<pair<int, int>> mecho_edge;
    mecho_edge.insert(mecho_pos);
    bool found = false;
    while(!found) {
        if(mecho_edge.size() == 0) {
            return false;
        }
        queue<pair<pair<int, int>, int>> q; // mecho queue
        for(auto iter : mecho_edge) {
            visited[iter.first][iter.second] = BEAR;
            q.push({iter, 0});
        }
        mecho_edge.clear();
        while(!q.empty()) {
            pair<pair<int, int>, int> curr = q.front();
            q.pop();
            if(curr.first.first + 1 < n && visited[curr.first.first + 1][curr.first.second] == UNVISITED && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first + 1][curr.first.second] = BEAR;
                    mecho_edge.insert({curr.first.first + 1, curr.first.second});
                } else {
                    visited[curr.first.first + 1][curr.first.second] = BEAR;
                    q.push({{curr.first.first + 1, curr.first.second}, curr.second + 1});
                }
            }
            if(curr.first.first - 1 >= 0 && visited[curr.first.first - 1][curr.first.second] == UNVISITED && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first - 1][curr.first.second] = BEAR;
                    mecho_edge.insert({curr.first.first - 1, curr.first.second});
                } else {
                    visited[curr.first.first - 1][curr.first.second] = BEAR;
                    q.push({{curr.first.first - 1, curr.first.second}, curr.second + 1});
                }
            }
            if(curr.first.second + 1 < n && visited[curr.first.first][curr.first.second + 1] == UNVISITED && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first][curr.first.second + 1] = BEAR;
                    mecho_edge.insert({curr.first.first, curr.first.second + 1});
                } else {
                    visited[curr.first.first][curr.first.second + 1] = BEAR;
                    q.push({{curr.first.first, curr.first.second + 1}, curr.second + 1});
                }
            }
            if(curr.first.second - 1 >= 0 && visited[curr.first.first][curr.first.second - 1] == UNVISITED && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first][curr.first.second - 1] = BEAR;
                    mecho_edge.insert({curr.first.first, curr.first.second - 1});
                } else {
                    visited[curr.first.first][curr.first.second - 1] = BEAR;
                    q.push({{curr.first.first, curr.first.second - 1}, curr.second + 1});
                }
            }
        }
        if(visited[home_pos.first][home_pos.second] == BEAR) {
            found = true;
            break;
        }
        vector<pair<int, int>> tmpedge;
        for(auto iter : bees_edge) {
            if(iter.first + 1 < n && visited[iter.first + 1][iter.second] == UNVISITED && grid[iter.first + 1][iter.second] == 'G') {
                visited[iter.first + 1][iter.second] = true;
                tmpedge.push_back({iter.first + 1, iter.second});
            }
            if(iter.first - 1 >= 0 && visited[iter.first - 1][iter.second] == UNVISITED && grid[iter.first - 1][iter.second] == 'G') {
                visited[iter.first - 1][iter.second] = true;
                tmpedge.push_back({iter.first - 1, iter.second});
            }
            if(iter.second + 1 < n && visited[iter.first][iter.second + 1] == UNVISITED && grid[iter.first][iter.second + 1] == 'G') {
                visited[iter.first][iter.second + 1] = true;
                tmpedge.push_back({iter.first, iter.second + 1});
            }
            if(iter.second - 1 >= 0 && visited[iter.first][iter.second - 1] == UNVISITED && grid[iter.first][iter.second - 1] == 'G') {
                visited[iter.first][iter.second - 1] = true;
                tmpedge.push_back({iter.first, iter.second - 1});
            }
        }
        bees_edge.clear();
        bees_edge = tmpedge;
    }
    if(found) {
        return true;
    } else {
        return false;
    }
}

int main() {
    cin >> n >> s;
    for(int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        for(int j = 0; j < n; j++) {
            grid[i][j] = tmp[j];
        }
    }
    int l = 0, r = n;
    int ans = -1;
    // true true true ... (true) false false
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 106 ms 6500 KB Output is correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Incorrect 1 ms 4700 KB Output isn't correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Incorrect 1 ms 2492 KB Output isn't correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 Incorrect 1 ms 2488 KB Output isn't correct
20 Incorrect 1 ms 2396 KB Output isn't correct
21 Incorrect 1 ms 2652 KB Output isn't correct
22 Incorrect 1 ms 2492 KB Output isn't correct
23 Incorrect 1 ms 2652 KB Output isn't correct
24 Incorrect 1 ms 2532 KB Output isn't correct
25 Incorrect 1 ms 4700 KB Output isn't correct
26 Incorrect 1 ms 4700 KB Output isn't correct
27 Incorrect 1 ms 4696 KB Output isn't correct
28 Incorrect 1 ms 4700 KB Output isn't correct
29 Incorrect 1 ms 4700 KB Output isn't correct
30 Incorrect 2 ms 4700 KB Output isn't correct
31 Incorrect 1 ms 4700 KB Output isn't correct
32 Incorrect 1 ms 4700 KB Output isn't correct
33 Incorrect 5 ms 4844 KB Output isn't correct
34 Incorrect 5 ms 4956 KB Output isn't correct
35 Correct 12 ms 5088 KB Output is correct
36 Incorrect 8 ms 4952 KB Output isn't correct
37 Incorrect 7 ms 4956 KB Output isn't correct
38 Correct 17 ms 4932 KB Output is correct
39 Incorrect 11 ms 4956 KB Output isn't correct
40 Incorrect 9 ms 5212 KB Output isn't correct
41 Correct 22 ms 5212 KB Output is correct
42 Incorrect 13 ms 5152 KB Output isn't correct
43 Incorrect 10 ms 5208 KB Output isn't correct
44 Correct 26 ms 5208 KB Output is correct
45 Incorrect 13 ms 5212 KB Output isn't correct
46 Incorrect 10 ms 5212 KB Output isn't correct
47 Correct 31 ms 5392 KB Output is correct
48 Incorrect 15 ms 5340 KB Output isn't correct
49 Incorrect 16 ms 5468 KB Output isn't correct
50 Correct 37 ms 5524 KB Output is correct
51 Incorrect 17 ms 5976 KB Output isn't correct
52 Incorrect 18 ms 5624 KB Output isn't correct
53 Correct 45 ms 5720 KB Output is correct
54 Incorrect 22 ms 5980 KB Output isn't correct
55 Incorrect 21 ms 5980 KB Output isn't correct
56 Correct 49 ms 5980 KB Output is correct
57 Incorrect 23 ms 5972 KB Output isn't correct
58 Incorrect 18 ms 6236 KB Output isn't correct
59 Correct 58 ms 6116 KB Output is correct
60 Incorrect 19 ms 6512 KB Output isn't correct
61 Incorrect 26 ms 6456 KB Output isn't correct
62 Correct 70 ms 6520 KB Output is correct
63 Correct 159 ms 6480 KB Output is correct
64 Incorrect 123 ms 6460 KB Output isn't correct
65 Correct 158 ms 6540 KB Output is correct
66 Incorrect 174 ms 6488 KB Output isn't correct
67 Correct 167 ms 6492 KB Output is correct
68 Correct 101 ms 6492 KB Output is correct
69 Correct 76 ms 6488 KB Output is correct
70 Correct 94 ms 6624 KB Output is correct
71 Correct 97 ms 6660 KB Output is correct
72 Correct 130 ms 6488 KB Output is correct
73 Correct 73 ms 7860 KB Output is correct
74 Correct 99 ms 6792 KB Output is correct
75 Correct 101 ms 6816 KB Output is correct
76 Correct 111 ms 6772 KB Output is correct
77 Correct 95 ms 6824 KB Output is correct
78 Correct 98 ms 7524 KB Output is correct
79 Correct 99 ms 6748 KB Output is correct
80 Correct 95 ms 6708 KB Output is correct
81 Correct 110 ms 6712 KB Output is correct
82 Correct 117 ms 6988 KB Output is correct
83 Correct 112 ms 7488 KB Output is correct
84 Correct 103 ms 6548 KB Output is correct
85 Correct 107 ms 6736 KB Output is correct
86 Correct 109 ms 7120 KB Output is correct
87 Correct 104 ms 6748 KB Output is correct
88 Correct 104 ms 7352 KB Output is correct
89 Correct 102 ms 6492 KB Output is correct
90 Correct 114 ms 7368 KB Output is correct
91 Correct 103 ms 6736 KB Output is correct
92 Correct 93 ms 7204 KB Output is correct