제출 #888469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888469		Billy_Nguyen	Mecho (IOI09_mecho)	C++17	0 / 100	169 ms	28240 KiB

mecho

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

#define x first
#define fastio()                 \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004; // Modular inverse of 2 modulo (10^9 + 7), also
                               // the number has to be in long long otherwise
                               // if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
vector<vector<char>> grid;
ll n, s;
pair<ll, ll> bear, home;
vector<pair<ll, ll>> hives;
vector<vector<ll>> beesDepths;
vector<vector<ll>> bearDepths;
bool valid = false;

void floodfill(ll i, ll j, vector<vector<bool>> &visited, ll mins)
{

    REP(k, 0, 4)
    {
        if (i + dy[k] < 1 || j + dx[k] < 1 || i + dy[k] > n || j + dx[k] > n)
        {
            continue;
        }

        if (visited[i + dy[k]][j + dx[k]])
        {
            continue;
        }

        if ((bearDepths[i + dy[k]][j + dx[k]] + 1) / s >=
            beesDepths[i + dy[k]][j + dx[k]] - mins)
        {
            continue;
        }

        if (grid[i + dy[k]][j + dx[k]] == 'D')
        {
            valid = true;
            return;
        }

        if (grid[i + dy[k]][j + dx[k]] != 'G')
        {
            continue;
        }


        visited[i][j] = true;
        floodfill(i + dy[k], j + dx[k], visited, mins);
    }
}

void solve()
{
    cin >> n >> s;

    grid.resize(n + 1);
    beesDepths.resize(n + 1);

    REP(i, 0, n + 1)
    {
        grid[i].resize(n + 1);
        beesDepths[i].resize(n + 1, 1e18);
    }

    REP(i, 1, n + 1)
    {
        REP(j, 1, n + 1)
        {
            cin >> grid[i][j];

            if (grid[i][j] == 'M')
            {
                bear = {i, j};
            }

            if (grid[i][j] == 'D')
            {
                home = {i, j};
            }

            if (grid[i][j] == 'H')
            {
                hives.PB({i, j});
            }
        }
    }

    deque<pair<pair<ll, ll>, ll>> q;

    REP(i, 0, hives.size())
    {
        q.PB(MP(hives[i], 0));
        beesDepths[hives[i].x][hives[i].y] = 0;
    }

    while (!q.empty())
    {
        pair<pair<ll, ll>, ll> cur = q.front();
        pair<ll, ll> coords = cur.x;
        ll d = cur.y;
        q.pop_front();

        REP(k, 0, 4)
        {
            if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
                coords.x + dy[k] > n || coords.y + dy[k] > n ||
                grid[coords.x + dy[k]][coords.y + dx[k]] != 'G')
            {
                continue;
            }

            if (beesDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1)
            {
                beesDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
                q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
            }
        }
    }

    ll l = 0;
    ll r = n * n;
    q.PB(MP(bear, 0));
    bearDepths.resize(n + 1);

    REP(i, 0, n + 1) { bearDepths[i].resize(n + 1, 1e18); }
    bearDepths[bear.x][bear.y] = 0;

    while (!q.empty())
    {
        pair<pair<ll, ll>, ll> cur = q.front();
        q.pop_front();

        pair<ll, ll> coords = cur.x;
        ll d = cur.y;

        REP(k, 0, 4)
        {
            if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
                coords.x + dy[k] > n || coords.y + dy[k] > n ||
                grid[coords.x + dy[k]][coords.y + dx[k]] != 'G')
            {
                continue;
            }

            if (bearDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1)
            {
                bearDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
                q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
            }
        }
    }

    while (l <= r)
    {
        ll mid = l + (r - l) / 2;
        vector<vector<bool>> bearVis(n + 1);
        valid = false;

        REP(i, 0, n + 1) { bearVis[i].resize(n + 1, false); }

        bearVis[bear.x][bear.y] = true;

        floodfill(bear.x, bear.y, bearVis, mid);
        if (valid)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }

        cout << l << " " << r << "\n";
    }

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

int main()
{
    fastio();
    solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'void solve()':
mecho.cpp:32:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 | #define REP(i, a, b) for (int i = a; i < b; i++)
......
  125 |     REP(i, 0, hives.size())
      |         ~~~~~~~~~~~~~~~~~~              
mecho.cpp:125:5: note: in expansion of macro 'REP'
  125 |     REP(i, 0, hives.size())
      |     ^~~

• Subtask 1: 0 / 100