Submission #1234155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234155		Ice_man	Maze (JOI23_ho_t3)	C++20	100 / 100	1174 ms	476148 KiB

Main

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <queue>

#define maxn 6000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define PB push_back
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")



typedef unsigned long long ull;
typedef std::pair <int, int> pii;
typedef long long ll;
typedef std::pair <ll, ll> pll;
typedef std::pair <int, ll> pil;
typedef std::pair <ll, int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}



int n, m, k;
std::string type[maxn];

pii start, endd;

pii dir[8] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
std::vector <std::vector <int> > ans, dist;

bool valid(pii node)
{
    return (node.X >= 0 && node.X < n && node.Y >= 0 && node.Y < m);
}

void read()
{
    std::cin >> n >> m >> k;

    std::cin >> start.X >> start.Y;
    std::cin >> endd.X >> endd.Y;

    start.X--;
    start.Y--;
    endd.X--;
    endd.Y--;

    for(int i = 0; i < n; i++)
        std::cin >> type[i];

    ans.resize(n + 5);
    dist.resize(n + 5);

    for(int i = 0; i < n + 5; i++)
        ans[i].resize(m + 5), dist[i].resize(m + 5);

    for(int i = 0; i < n + 5; i++)
        for(int j = 0; j < m + 5; j++)
            ans[i][j] = dist[i][j] = -1;

    std::vector <pii> w, b;
    w.PB(start);

    for(int i = 0; i < n + m + 2; i++)
    {
        if(i > 0)
        {
            std::queue <pii> q;

            for(auto& e : b)
            {
                if(ans[e.X][e.Y] != -1)
                    continue;
                q.push(e);
                dist[e.X][e.Y] = 0;
            }

            b.clear();

            while(q.size() != 0)
            {
                pii node = q.front();
                q.pop();

                if(ans[node.X][node.Y] != -1)
                    continue;
                ans[node.X][node.Y] = i;

                for(auto& d : dir)
                {
                    pii nb = {node.X + d.X, node.Y + d.Y};
                    if(valid(nb) == false)
                        continue;
                    int dd = dist[node.X][node.Y] + 1;

                    if(dist[nb.X][nb.Y] != -1 && dist[nb.X][nb.Y] <= dd)
                        continue;

                    if(ans[nb.X][nb.Y] != -1)
                        continue;

                    if(dd >= k)
                    {
                        if(abs(d.X) + abs(d.Y) == 1)
                        {
                            if(type[nb.X][nb.Y] == '.')
                                w.PB(nb);
                            else
                                b.PB(nb);
                        }

                        continue;
                    }

                    dist[nb.X][nb.Y] = dd;
                    q.push(nb);
                }
            }
        }


        std::queue <pii> q;
        for(auto& e : w)
        {
            if(ans[e.X][e.Y] != -1)
                continue;
            q.push(e);
        }

        w.clear();
        while(q.size() != 0)
        {
            pii node = q.front();
            q.pop();

            if(ans[node.X][node.Y] != -1)
                continue;
            ans[node.X][node.Y] = i;

            for(auto& d : dir)
            {
                if(abs(d.X) + abs(d.Y) != 1)
                    continue;

                pii nb = {node.X + d.X , node.Y + d.Y};
                if(valid(nb) == false)
                    continue;
                if(ans[nb.X][nb.Y] != -1)
                    continue;
                if(type[nb.X][nb.Y] == '.')
                    q.push(nb);
                else
                    b.PB(nb);
            }
        }
    }

    std::cout << ans[endd.X][endd.Y] << "\n";
}













int main()
{

    /**#ifdef ONLINE_JUDGE /// promeni
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif*/

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();


    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6