Submission #689588

#	Time	Username	Problem	Language	Result	Execution time	Memory
689588		pls33	Mecho (IOI09_mecho)	C++17	74 / 100	360 ms	13904 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

using grid_t = vector<string>;

const vi32 dx = {1, -1, 0, 0};
const vi32 dy = {0, 0, 1, -1};

struct frac_t
{
    int64_t enumer, denomin;

    frac_t(int64_t e = 0, int64_t d = 1)
    {
        enumer = e;
        denomin = d;
    }

    frac_t operator+(frac_t rhs)
    {
        int64_t d = lcm(denomin, rhs.denomin);
        int64_t e = enumer * (d / denomin) + rhs.enumer * (d / rhs.denomin);

        return {e, d};
    }

    bool operator<(frac_t rhs)
    {
        int64_t d = lcm(denomin, rhs.denomin);
        return enumer * (d / denomin) < rhs.enumer * (d / rhs.denomin);
    }

    bool operator>=(frac_t rhs)
    {
        int64_t d = lcm(denomin, rhs.denomin);
        return enumer * (d / denomin) >= rhs.enumer * (d / rhs.denomin);
    }

    bool operator<(int64_t rhs)
    {
        return *this < frac_t(rhs, 1);
    }

    bool operator>=(int64_t rhs)
    {
        return *this >= frac_t(rhs, 1);
    }

    double approx()
    {
        return (double)enumer / (double)denomin;
    }
};

using bear_t = vector<vector<frac_t>>;

bool inside(p32 pos, int n)
{
    return pos.first >= 0 && pos.first < n &&
           pos.second >= 0 && pos.second < n;
}

void get_time(vp32 &hive, vvi32 &reach_time, grid_t &grid)
{
    queue<p32> q;
    for (auto &h : hive)
    {
        q.push(h);
        reach_time[h.first][h.second] = 0;
    }

    while (!q.empty())
    {
        p32 cur = q.front();
        q.pop();

        for (int i = 0; i < (int)dx.size(); i++)
        {
            p32 next = {cur.first + dx[i], cur.second + dy[i]};

            if (inside(next, (int)grid.size()) && grid[next.first][next.second] == 'M' &&
                reach_time[next.first][next.second] == INT_MAX)
            {
                reach_time[next.first][next.second] = reach_time[cur.first][cur.second] + 1;
            }

            if (!inside(next, (int)grid.size()) ||
                grid[next.first][next.second] != 'G' ||
                reach_time[next.first][next.second] != INT_MAX)
            {
                continue;
            }

            reach_time[next.first][next.second] = reach_time[cur.first][cur.second] + 1;
            q.push(next);
        }
    }
}

bool can_reach(p32 start, p32 end, int time, frac_t speed,
               vvi32 &reach_time, bear_t &bear_time, grid_t &grid)
{
    if (time >= reach_time[start.first][start.second])
    {
        return false;
    }
    bear_time[start.first][start.second] = frac_t(time, 1);
    queue<p32> q;
    q.push(start);

    while (!q.empty())
    {
        p32 cur = q.front();
        q.pop();

        for (int i = 0; i < (int)dx.size(); i++)
        {
            p32 next = {cur.first + dx[i], cur.second + dy[i]};
            frac_t cur_time = bear_time[cur.first][cur.second] + speed;

            if (!inside(next, (int)grid.size()) ||
                (grid[next.first][next.second] != 'G' &&
                 grid[next.first][next.second] != 'D') ||
                bear_time[next.first][next.second].enumer != -1 ||
                cur_time >= reach_time[next.first][next.second])
            {
                continue;
            }

            bear_time[next.first][next.second] = cur_time;

            if (next == end)
            {
                return true;
            }

            q.push(next);
        }
    }

    return false;
}

bool test_reach(p32 start, p32 end, int time, int s,
                vvi32 &reach_time, bear_t &bear_time, grid_t &grid)
{
    frac_t speed(1, s);
    bool result = can_reach(start, end, time, speed, reach_time, bear_time, grid);

    for (auto &row : bear_time)
    {
        for (auto &b : row)
        {
            b = frac_t(-1, 1);
        }
    }

    return result;
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("mecho.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int n, s;
    cin >> n >> s;

    grid_t grid(n);
    vp32 hive;
    p32 start, end;
    {
        int i = 0;
        for (auto &row : grid)
        {
            cin >> row;
            for (int j = 0; j < (int)row.size(); j++)
            {
                switch (row[j])
                {
                case 'M':
                {
                    start = {i, j};
                    break;
                }
                case 'D':
                {
                    end = {i, j};
                    break;
                }
                case 'H':
                {
                    hive.emplace_back(i, j);
                    break;
                }
                }
            }

            i++;
        }
    }

    vvi32 reach_time(n, vi32(n, INT_MAX));
    bear_t bear_time(n, vector<frac_t>(n, frac_t(-1, -1)));
    get_time(hive, reach_time, grid);

    int result = 0;
    for (int bit = 10; bit >= 0; bit--)
    {
        int cur = result + (1 << bit);
        if (cur > n * n || !test_reach(start, end, cur, s, reach_time, bear_time, grid))
        {
            continue;
        }

        result = cur;
    }

    if (!result)
    {
        bool cant = !test_reach(start, end, 0, s, reach_time, bear_time, grid);
        result = cant ? -1 : result;
    }
    cout << result << '\n';

    return 0;
}

Compilation message (stderr)

mecho.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
mecho.cpp:31: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   31 | #pragma endregion
      |

• Subtask 1: 74 / 100