Submission #1091349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091349		conthoanco	Mecho (IOI09_mecho)	C++14	95 / 100	127 ms	7028 KiB

mecho

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 805;

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

int n, s;
char c[N][N];
pair<int, int> hive, house, bear;
int mecho[N][N], bee[N][N];

bool check(int time)
{
    memset(mecho, -1, sizeof(mecho));
    mecho[bear.fi][bear.se] = 0;
    if(bee[bear.fi][bear.se] <= time) return false;
    queue<pair<int, int>> p;
    p.push(bear);

    while(p.size())
    {
        int u = p.front().fi;
        int v = p.front().se;
        p.pop();
        for(int e = 0; e < 4; e ++)
        {
            int nu = u + dx[e];
            int nv = v + dy[e];
            if(nu < 1 || nu > n) continue;
            if(nv < 1 || nv > n) continue;
            if(mecho[nu][nv] == -1 && c[nu][nv] != 'T')
            {
                if((mecho[u][v] + 1)/s + time < bee[nu][nv])
                {
                    mecho[nu][nv] = mecho[u][v] + 1;
                    p.push({nu, nv});
                }
            }
        }
    }

    for(int e = 0; e < 4; e ++)
    {
        if(house.fi + dx[e] < 1 || house.fi + dx[e] > n) continue;
        if(house.se + dy[e] < 1 || house.se + dy[e] > n) continue;
        if(c[house.fi + dx[e]][house.se + dy[e]] == 'T') continue;
        if(c[house.fi + dx[e]][house.se + dy[e]] == 'H') continue;
        if(mecho[house.fi + dx[e]][house.se + dy[e]] != -1) return true;
    }

    return false;
}

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

    cin >> n >> s;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            cin >> c[i][j];
            if(c[i][j] == 'M')
                bear = {i, j};
            if(c[i][j] == 'D')
                house = {i, j};
        }
    memset(bee, -1, sizeof(bee));

    queue<pair<int, int>> q;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++){
            if(c[i][j] == 'H')
            {
                bee[i][j] = 0;
                q.push({i, j});
            }

        }
    while(q.size())
    {
        int u = q.front().fi;
        int v = q.front().se;
        q.pop();
        for(int e = 0; e < 4; e ++)
        {
            int nu = u + dx[e];
            int nv = v + dy[e];
            if(nu < 1 || nu > n) continue;
            if(nv < 1 || nv > n) continue;
            if(bee[nu][nv] == -1 && c[nu][nv] != 'T')
            {
                bee[nu][nv] = bee[u][v] + 1;
                q.push({nu, nv});
            }
        }
    }

    int l = 0, r = 1e9, ans = -1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    cout << ans;
}

• Subtask 1: 95 / 100