Submission #1186553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186553		Zbyszek99	Maze (JOI23_ho_t3)	C++20	100 / 100	1526 ms	1073660 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int r,c,n;

string plane[6'000'001];
int dist[12'000'001];
vector<pii> dir4 = {{1,0},{-1,0},{0,1},{0,-1}};
vector<pii> dir8 = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> r >> c >> n;
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    sx--;
    sy--;
    ex--;
    ey--;
    int beg_cell = sx * c + sy;
    int end_cell = ex * c + ey;
    rep(i,r) cin >> plane[i];
    rep(i,12'000'001) dist[i] = 1e9;
    deque<pair<pii,pii>> q;
    q.push_front({{0,0},{sx,sy}});
    while(!q.empty())
    {
        pair<pii,pii> t = q.front();
        q.pop_front();
        int cell = t.ss.ff * c + t.ss.ss + c*r * t.ff.ss;
        if(dist[cell] != 1e9) continue;
        dist[cell] = t.ff.ff;
       // cout << t.ff.ff << " " << t.ss.ff << " " << t.ss.ss << " " << t.ff.ss << " dij\n";
        if(t.ff.ss == 0)
        {
            forall(d,dir4)
            {
                int new_x = t.ss.ff + d.ff;
                int new_y = t.ss.ss + d.ss;
                if(new_x >= 0 && new_x < r && new_y >= 0 && new_y < c)
                {
                    if(plane[new_x][new_y] == '.')
                    {
                        q.push_front({{t.ff.ff,0},{new_x,new_y}});
                    }
                    q.push_back({{t.ff.ff+1,1},{new_x,new_y}});
                }
            }
        }
        else
        {
            if(t.ff.ff % n == 0)
            {
                q.push_front({{t.ff.ff,0},t.ss});
            }
            else
            {
                forall(d,dir8)
                {
                    int new_x = t.ss.ff + d.ff;
                    int new_y = t.ss.ss + d.ss;
                    if(new_x >= 0 && new_x < r && new_y >= 0 && new_y < c)
                    {
                        q.push_back({{t.ff.ff+1,1},{new_x,new_y}});
                    }
                }
            }
        }
    }
    cout << (min(dist[end_cell],dist[end_cell+r*c]) + n-1) / n;
}

• 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