Submission #965873

#	Time	Username	Problem	Language	Result	Execution time	Memory
965873		OIaspirant2307	Mecho (IOI09_mecho)	C++17	18 / 100	68 ms	12632 KiB

mecho

#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 - 1 << '\n';
}

• Subtask 1: 18 / 100