oj.uz

Submission #965879

# Submission time Handle Problem Language Result Execution time Memory
965879 2024-04-19T07:43:51 Z OIaspirant2307 Mecho (IOI09_mecho) C++17
16 / 100
 75 ms 11868 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
#define int long long
#define pi pair<int, int>
#define f first
#define s second
const int N = 805;
const int INF = 1e10;
vector<vector<char>> grid(N, vector<char>(N));
vector<vector<int>> vis(N, vector<int>(N, INF));
vector<vector<int>> v(N, vector<int>(N, INF));
vector<pi> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<pi> bees;
pi mecho;
pi loc;
int n, m;
int steps;
 
bool ok(int i, int j, int val)
{
    return (i >= 0 && i < n && j >= 0 && j < m && vis[i][j] > val && grid[i][j] != 'T');
}
bool ok2(int i, int j, int val)
{
    return (i >= 0 && i < n && j >= 0 && j < m && v[i][j] > val && grid[i][j] != 'T');
}
 
void bee_bfs()
{
    queue<pi> q;
    for (auto p : bees)
    {
        vis[p.f][p.s] = 0;
        q.push(p);
    }
    while (!q.empty())
    {
        auto p = q.front();
        q.pop();
        for (auto mv : moves)
        {
            int val = vis[p.f][p.s] + 1;
            if (ok(p.f + mv.f, p.s + mv.s, val))
            {
                vis[p.f + mv.f][p.s + mv.s] = val;
                q.push({p.f + mv.f, p.s + mv.s});
            }
        }
    }
}
 
void mecho_bfs()
{
    queue<pi> q;
    v[mecho.f][mecho.s] = 0;
    q.push(mecho);
    while (!q.empty())
    {
        auto p = q.front();
        q.pop();
        for (auto mv : moves)
        {
            int val = v[p.f][p.s] + 1;
            if (ok2(p.f + mv.f, p.s + mv.s, val))
            {
                v[p.f + mv.f][p.s + mv.s] = val;
                q.push({p.f + mv.f, p.s + mv.s});
            }
        }
    }
}
bool issoke(int t)
{
    return (((v[loc.f][loc.s]) / steps) + t) < (vis[loc.f][loc.s]);
}
 
signed main()
{
    cin >> n >> steps;
    m = n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> grid[i][j];
            if (grid[i][j] == 'M')
            {
                mecho.f = i;
                mecho.s = j;
            }
            else if (grid[i][j] == 'H')
            {
                bees.push_back({i, j});
            }
            else if (grid[i][j] == 'D')
            {
                loc.f = i;
                loc.s = j;
            }
        }
    }
    bee_bfs();
    mecho_bfs();
    if (!issoke(0))
    {
        cout << -1 << '\n';
        return 0;
    }
    int l = 0;
    int r = 1;
    while (issoke(r))
    {
        r *= 2;
    }
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
        if (issoke(m))
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }
    cout << l << '\n';
}

Subtask #1
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11100 KB Output is correct
2 Incorrect 5 ms 11100 KB Output isn't correct
3 Correct 6 ms 11128 KB Output is correct
4 Incorrect 5 ms 11096 KB Output isn't correct
5 Incorrect 6 ms 11100 KB Output isn't correct
6 Incorrect 7 ms 11096 KB Output isn't correct
7 Incorrect 55 ms 11284 KB Output isn't correct
8 Correct 6 ms 11100 KB Output is correct
9 Incorrect 5 ms 11100 KB Output isn't correct
10 Incorrect 6 ms 11100 KB Output isn't correct
11 Incorrect 6 ms 11096 KB Output isn't correct
12 Incorrect 7 ms 11100 KB Output isn't correct
13 Incorrect 6 ms 11100 KB Output isn't correct
14 Correct 6 ms 11100 KB Output is correct
15 Correct 6 ms 11352 KB Output is correct
16 Incorrect 5 ms 11096 KB Output isn't correct
17 Correct 6 ms 11100 KB Output is correct
18 Incorrect 7 ms 11100 KB Output isn't correct
19 Correct 6 ms 11100 KB Output is correct
20 Incorrect 6 ms 11100 KB Output isn't correct
21 Correct 6 ms 11100 KB Output is correct
22 Incorrect 6 ms 11096 KB Output isn't correct
23 Correct 6 ms 11100 KB Output is correct
24 Incorrect 6 ms 11096 KB Output isn't correct
25 Correct 8 ms 11100 KB Output is correct
26 Incorrect 6 ms 11100 KB Output isn't correct
27 Correct 6 ms 11100 KB Output is correct
28 Incorrect 6 ms 11100 KB Output isn't correct
29 Correct 6 ms 11352 KB Output is correct
30 Incorrect 6 ms 11100 KB Output isn't correct
31 Correct 6 ms 11096 KB Output is correct
32 Incorrect 6 ms 11100 KB Output isn't correct
33 Correct 12 ms 11244 KB Output is correct
34 Incorrect 11 ms 11096 KB Output isn't correct
35 Incorrect 15 ms 11096 KB Output isn't correct
36 Correct 14 ms 11100 KB Output is correct
37 Incorrect 13 ms 11100 KB Output isn't correct
38 Incorrect 18 ms 11100 KB Output isn't correct
39 Correct 16 ms 11100 KB Output is correct
40 Incorrect 15 ms 11100 KB Output isn't correct
41 Incorrect 20 ms 11100 KB Output isn't correct
42 Correct 18 ms 11100 KB Output is correct
43 Incorrect 18 ms 11096 KB Output isn't correct
44 Incorrect 23 ms 11100 KB Output isn't correct
45 Correct 21 ms 11352 KB Output is correct
46 Incorrect 22 ms 11100 KB Output isn't correct
47 Incorrect 27 ms 11292 KB Output isn't correct
48 Correct 24 ms 11100 KB Output is correct
49 Incorrect 23 ms 11100 KB Output isn't correct
50 Incorrect 43 ms 11100 KB Output isn't correct
51 Correct 27 ms 11296 KB Output is correct
52 Incorrect 25 ms 11100 KB Output isn't correct
53 Incorrect 40 ms 11100 KB Output isn't correct
54 Correct 31 ms 11292 KB Output is correct
55 Incorrect 41 ms 11100 KB Output isn't correct
56 Incorrect 57 ms 11276 KB Output isn't correct
57 Correct 40 ms 11100 KB Output is correct
58 Incorrect 33 ms 11096 KB Output isn't correct
59 Incorrect 46 ms 11100 KB Output isn't correct
60 Correct 40 ms 11100 KB Output is correct
61 Incorrect 36 ms 11096 KB Output isn't correct
62 Incorrect 54 ms 11280 KB Output isn't correct
63 Incorrect 56 ms 11280 KB Output isn't correct
64 Incorrect 61 ms 11276 KB Output isn't correct
65 Incorrect 61 ms 11284 KB Output isn't correct
66 Incorrect 56 ms 11284 KB Output isn't correct
67 Incorrect 55 ms 11280 KB Output isn't correct
68 Incorrect 58 ms 11356 KB Output isn't correct
69 Incorrect 75 ms 11368 KB Output isn't correct
70 Incorrect 57 ms 11340 KB Output isn't correct
71 Incorrect 57 ms 11336 KB Output isn't correct
72 Incorrect 64 ms 11292 KB Output isn't correct
73 Incorrect 53 ms 11856 KB Output isn't correct
74 Correct 56 ms 11868 KB Output is correct
75 Incorrect 56 ms 11864 KB Output isn't correct
76 Correct 56 ms 11868 KB Output is correct
77 Incorrect 54 ms 11868 KB Output isn't correct
78 Correct 53 ms 11596 KB Output is correct
79 Incorrect 55 ms 11596 KB Output isn't correct
80 Incorrect 56 ms 11600 KB Output isn't correct
81 Incorrect 57 ms 11612 KB Output isn't correct
82 Incorrect 53 ms 11604 KB Output isn't correct
83 Incorrect 57 ms 11600 KB Output isn't correct
84 Correct 61 ms 11612 KB Output is correct
85 Incorrect 60 ms 11724 KB Output isn't correct
86 Incorrect 73 ms 11540 KB Output isn't correct
87 Incorrect 57 ms 11604 KB Output isn't correct
88 Incorrect 58 ms 11612 KB Output isn't correct
89 Correct 55 ms 11612 KB Output is correct
90 Incorrect 60 ms 11608 KB Output isn't correct
91 Incorrect 56 ms 11604 KB Output isn't correct
92 Incorrect 59 ms 11600 KB Output isn't correct