oj.uz

Submission #566138

# Submission time Handle Problem Language Result Execution time Memory
566138 2022-05-21T21:45:42 Z faruk Mecho (IOI09_mecho) C++17
39 / 100
 229 ms 3152 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double

using namespace std;

vector<string> grid;
int n, s;

void expand(queue<pii>& bees, vector<string>& mat, vector<vector<bool> > &expanded ) {

    queue<pii> newque;
    while (!bees.empty()) {
        pii curr = bees.front();
        bees.pop();

        if (expanded[curr.first][curr.second])
            continue;
        
        if (mat[curr.first + 1][curr.second] == 'G' || mat[curr.first + 1][curr.second] == 'M')
            mat[curr.first + 1][curr.second] = 'H', newque.push({curr.first + 1, curr.second});
        if (mat[curr.first - 1][curr.second] == 'G' || mat[curr.first - 1][curr.second] == 'M')
            mat[curr.first - 1][curr.second] = 'H', newque.push({curr.first - 1, curr.second});
        if (mat[curr.first][curr.second + 1] == 'G' || mat[curr.first][curr.second + 1] == 'M')
            mat[curr.first][curr.second + 1] = 'H', newque.push({curr.first, curr.second + 1});
        if (mat[curr.first][curr.second - 1] == 'G' || mat[curr.first][curr.second - 1] == 'M')
            mat[curr.first][curr.second - 1] = 'H', newque.push({curr.first, curr.second - 1});
        expanded[curr.first][curr.second] = true;
    }

    bees = newque;
}

bool possible(int wait, queue<pii> bees, pii start, pii endd) {
    vector<vector<bool> > expanded(n + 2, vector<bool>(n + 2, false));
    vector<string> mat = grid;

    for (int i = 0; i < wait; i++)
        expand(bees, mat, expanded);

    vector<vector<bool> > visited(n + 2, vector<bool>(n + 2, false));
    int tim = s;
    queue<pair<int, pii> > que;

    grid[start.first][start.second] = 'G';
    grid[endd.first][endd.second] = 'G';
    que.push({0, {start.first, start.second}});
    while (!que.empty())
    {
        pair<int, pii> curr = que.front();
        que.pop();

        if (curr.first == tim) {
            expand(bees, mat, expanded);
            tim += s;
        }

        if (mat[curr.second.first][curr.second.second] != 'G' || visited[curr.second.first][curr.second.second])
            continue;
        visited[curr.second.first][curr.second.second] = true;

        que.push({curr.first + 1, {curr.second.first + 1, curr.second.second}});
        que.push({curr.first + 1, {curr.second.first - 1, curr.second.second}});
        que.push({curr.first + 1, {curr.second.first, curr.second.second + 1}});
        que.push({curr.first + 1, {curr.second.first, curr.second.second - 1}});
    }
    
    return visited[endd.first][endd.second];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    grid.resize(n + 2);
    string wall;
    for (int i = 0; i < n + 2; i++)
        wall += 'T';
    grid[0] = wall, grid[n + 1] = wall;
    for (int i = 1; i <= n; i++) {
        string curr = "T";
        string inp;
        cin >> inp;
        curr += inp;
        curr += 'T';
        grid[i] = curr;
    }

    queue<pii> bees;
    pii start, endd;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == 'D')
                endd = {i, j};
            else if (grid[i][j] == 'H')
                bees.push({i, j});
            else if (grid[i][j] == 'M')
                start = {i, j};
        }
    }
    
    int l = 0, r = 2 * n;
    while (l < r) {
        int mid = (l + r) / 2;
        if (possible(mid, bees, start, endd))
            l = 1 + mid;
        else
            r = mid;
    }

    cout << l - 1 << "\n";
}

Subtask #1
39.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 324 KB Output isn't correct
7 Incorrect 198 ms 2680 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 324 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Incorrect 1 ms 340 KB Output isn't correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Incorrect 2 ms 340 KB Output isn't correct
28 Incorrect 2 ms 340 KB Output isn't correct
29 Incorrect 2 ms 340 KB Output isn't correct
30 Incorrect 2 ms 340 KB Output isn't correct
31 Incorrect 2 ms 340 KB Output isn't correct
32 Incorrect 2 ms 320 KB Output isn't correct
33 Incorrect 35 ms 688 KB Output isn't correct
34 Incorrect 25 ms 724 KB Output isn't correct
35 Correct 35 ms 808 KB Output is correct
36 Incorrect 46 ms 980 KB Output isn't correct
37 Incorrect 30 ms 836 KB Output isn't correct
38 Correct 50 ms 940 KB Output is correct
39 Incorrect 58 ms 1056 KB Output isn't correct
40 Incorrect 38 ms 980 KB Output isn't correct
41 Correct 62 ms 980 KB Output is correct
42 Incorrect 71 ms 1236 KB Output isn't correct
43 Incorrect 52 ms 1236 KB Output isn't correct
44 Correct 96 ms 1256 KB Output is correct
45 Incorrect 95 ms 1364 KB Output isn't correct
46 Incorrect 66 ms 1360 KB Output isn't correct
47 Correct 93 ms 1440 KB Output is correct
48 Incorrect 110 ms 1612 KB Output isn't correct
49 Incorrect 77 ms 1620 KB Output isn't correct
50 Correct 123 ms 1776 KB Output is correct
51 Incorrect 132 ms 1748 KB Output isn't correct
52 Incorrect 88 ms 1816 KB Output isn't correct
53 Correct 129 ms 1856 KB Output is correct
54 Incorrect 154 ms 2028 KB Output isn't correct
55 Incorrect 103 ms 2040 KB Output isn't correct
56 Correct 155 ms 2060 KB Output is correct
57 Incorrect 175 ms 2184 KB Output isn't correct
58 Incorrect 119 ms 2260 KB Output isn't correct
59 Correct 171 ms 2260 KB Output is correct
60 Incorrect 200 ms 2492 KB Output isn't correct
61 Incorrect 134 ms 2528 KB Output isn't correct
62 Correct 219 ms 2684 KB Output is correct
63 Correct 170 ms 2672 KB Output is correct
64 Incorrect 229 ms 2524 KB Output isn't correct
65 Correct 188 ms 2548 KB Output is correct
66 Correct 205 ms 2632 KB Output is correct
67 Correct 184 ms 2548 KB Output is correct
68 Correct 125 ms 2592 KB Output is correct
69 Correct 87 ms 2536 KB Output is correct
70 Correct 99 ms 2528 KB Output is correct
71 Correct 100 ms 2712 KB Output is correct
72 Correct 140 ms 2516 KB Output is correct
73 Correct 102 ms 3108 KB Output is correct
74 Correct 186 ms 2964 KB Output is correct
75 Correct 210 ms 3084 KB Output is correct
76 Correct 187 ms 2980 KB Output is correct
77 Correct 205 ms 2984 KB Output is correct
78 Correct 220 ms 3152 KB Output is correct
79 Correct 203 ms 2912 KB Output is correct
80 Correct 207 ms 2996 KB Output is correct
81 Correct 214 ms 2900 KB Output is correct
82 Correct 182 ms 2932 KB Output is correct
83 Correct 225 ms 2996 KB Output is correct
84 Correct 206 ms 2816 KB Output is correct
85 Correct 195 ms 2852 KB Output is correct
86 Correct 221 ms 2964 KB Output is correct
87 Correct 195 ms 2824 KB Output is correct
88 Correct 220 ms 2752 KB Output is correct
89 Correct 213 ms 2752 KB Output is correct
90 Correct 223 ms 2752 KB Output is correct
91 Correct 222 ms 2748 KB Output is correct
92 Correct 197 ms 2836 KB Output is correct