Submission #858188

#	Time	Username	Problem	Language	Result	Execution time	Memory
858188		BBart888	Mecho (IOI09_mecho)	C++14	68 / 100	177 ms	10644 KiB

mecho

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <stdio.h>      /* printf, scanf, puts, NULL */
#include <stdlib.h>     /* srand, rand */
#include <time.h> 
#include <unordered_map>
#include <string>
#include <fstream>



using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Mat = vector<vector<ll>>;

const ll MOD = 2019201997LL;
const ll FACTOR1 = 2019201913LL;
const ll FACTOR2 = 2019201949LL;
const int MAXN = 1e3 + 11;




int n, s, l, r;
char t[MAXN][MAXN];
vector<pair<int,int>>hives;
int dx[]{ 0,0,-1,1 };
int dy[]{ 1,-1,0,0 };
int dist[MAXN][MAXN];
pair<int, int> bear,house;




bool within(int x, int y)
{
    return (x >= 0 && y >= 0 && x < n&& y < n);
}

bool reached(int mecho, int bees)
{
    return mecho / s < bees;
}


void action()
{
    queue<pair<int, int>> q;
    vector<vector<int>> vis(n, vector<int>(n));

    for (auto h : hives)
    {
        q.push(h);
        vis[h.first][h.second] = true;
    }

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int d = 0; d < 4; d++)
        {
            int newX = x + dx[d];
            int newY = y + dy[d];
            if (!within(newX, newY) || (t[newX][newY] != 'G' && t[newX][newY] != 'M')
                || vis[newX][newY])
                continue;
            vis[newX][newY] = true;
            q.push({ newX,newY });
            dist[newX][newY] = dist[x][y] + 1;
        }
    }
    

}



bool check(int mins)
{
    queue<pair<int,int>> q;
    vector<vector<int>>bear_dist(n, vector<int>(n));
    vector<vector<int>> vis(n, vector<int>(n));

    q.push(bear);
    vis[bear.first][bear.second] = true;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        //cout << x << " " << y << " " << bear_dist[x][y] <<" VS "<<
           // dist[x][y]<<'\n';
        for (int d = 0; d < 4; d++)
        {
            int newX = x + dx[d];
            int newY = y + dy[d];
            if (!within(newX, newY) || (t[newX][newY] != 'G' && t[newX][newY] != 'M') || (
                !reached(bear_dist[x][y]+1,dist[newX][newY]-mins)) || vis[newX][newY])
                continue;
            vis[newX][newY] = true;
            q.push({ newX,newY });
            bear_dist[newX][newY] = bear_dist[x][y] + 1;
        }

    }
    int flag = 0;

    for (int d = 0; d < 4; d++)
    {
        int Hx = house.first + dx[d];
        int Hy = house.second + dy[d];
        if (!within(Hx, Hy))
            continue;
        if (vis[Hx][Hy])
            flag = 1;
    }

    return flag;
}



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

    //freopen("lasers.in", "r", stdin);
    //freopen("lasers.out", "w", stdout);


    cin >> n >> s;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> t[i][j];
            if (t[i][j] == 'H')
                hives.push_back({ i,j });
            if (t[i][j] == 'M')
                bear = { i,j };
            if (t[i][j] == 'D')
                house = { i,j };
        }
    }


    action();

    
    int l = 0, r = n * n;
    while (l < r)
    {
        int m = (l + r + 1) / 2;
        if (check(m))
            l = m;
        else
            r = m - 1;
    }

    if (l == n * n)
        cout << -1 << '\n';
    else
        cout << l << '\n';




    return 0;
}

• Subtask 1: 68 / 100