Submission #1188106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188106		user736482	Maze (JOI23_ho_t3)	C++20	94 / 100	2097 ms	1829936 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,r,c,d,t,n,m,l,q,k,ak,ans,s;
vector<ll>g[6000000],g2[6000000],g3[6000000];
bool co[6000000];
ll dst[6000000];
bool odw[6000000];
ll in(){
    ll x=0;
    char ch=getchar_unlocked();
    while(ch>'9' || ch<'0')ch=getchar_unlocked();
    while(ch>='0' && ch<='9'){
        x*=10;
        x+=ch-'0';
        ch=getchar_unlocked();
    }
    return x;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    c=in();r=in();n=in();
    b=in();a=in();
    a--;b--;
    s=r*b+a;
    b=in();a=in();
    a--;b--;
    t=r*b+a;
    for(ll i=0;i<r*c;i++){
        char ch;
        ch=getchar_unlocked();
        while(ch!='.' && ch!='#')ch=getchar_unlocked();
        co[i]=(ch=='.');
    }
    for(ll i=0;i<r*c;i++){
        if(i>=r){
            if(co[i])
            g[i].pb(i-r);
            g2[i].pb(i-r);
        }
        if(i+r<r*c){
            if(co[i])
            g[i].pb(i+r);
            g2[i].pb(i+r);
        }
        if(i%r<r-1){
            if(co[i])
            g[i].pb(i+1);
            g2[i].pb(i+1);
        }
        if(i%r){
            if(co[i])
            g[i].pb(i-1);
            g2[i].pb(i-1);
        }
        swap(g3[i],g2[i]);
        if(i%r && i>=r){
            g2[i].pb(i-r-1);
        }
        if(i%r<r-1 && i>=r){
            g2[i].pb(i-r+1);
        }
        if(i%r && i+r<r*c){
            g2[i].pb(i+r-1);
        }
        if(i%r<r-1 && i+r<r*c){
            g2[i].pb(i+r+1);
        }
    }
    deque<pair<ll,ll>>pq;
    pq.pb({0,s});
    while(pq.size()){
        auto pom=pq.front();
        pq.pop_front();
        if(odw[pom.ss])continue;
        odw[pom.ss]=1;
        dst[pom.ss]=pom.ff;
        if(pom.ff%n!=n-1){
            for(ll i : g2[pom.ss]){
                pq.pb({pom.ff+1,i});
            }
        }

            for(ll i : g3[pom.ss]){
            pq.pb({pom.ff+1,i});
        
        }
        if(pom.ff%n==0){
            for(ll i : g[pom.ss]){
                pq.push_front({pom.ff,i});
            }
        }
    }
    cout<<(dst[t]+n-1)/n;
    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: 0 / 6