제출 #1188155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188155		user736482	Maze (JOI23_ho_t3)	C++20	100 / 100	735 ms	568792 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
#pragma GCC target("avx2")
#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;

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=='.');
    }
    deque<pair<ll,ll>>pq;
    pq.pb({0,s});
    while(pq.size()){
        auto pom=pq.front();
        pq.pop_front();
        if(pom.ss<0 || pom.ss>=r*c || odw[pom.ss] )continue;
        odw[pom.ss]=1;
        dst[pom.ss]=pom.ff;
        auto pomm=pom.ff%n;
        if(pomm!=n-1){
            if(pom.ss%r<r-1){
                pq.pb({pom.ff+1,pom.ss+1+r});
                pq.pb({pom.ff+1,pom.ss+1-r});
            }
            if(pom.ss%r){
                pq.pb({pom.ff+1,pom.ss-1-r});
                pq.pb({pom.ff+1,pom.ss-1+r});
            }
        }

            
        if(pomm%n==0 && co[pom.ss]){
                pq.push_front({pom.ff,pom.ss+r});
            pq.push_front({pom.ff,pom.ss-r});
            if(pom.ss%r<r-1){
                pq.push_front({pom.ff,pom.ss+1});
            }
            if(pom.ss%r){
                pq.push_front({pom.ff,pom.ss-1});
            }
            }
        
        else{
            pq.pb({pom.ff+1,pom.ss+r});
            pq.pb({pom.ff+1,pom.ss-r});
            if(pom.ss%r<r-1){
                pq.pb({pom.ff+1,pom.ss+1});
            }
            if(pom.ss%r){
                pq.pb({pom.ff+1,pom.ss-1});
            }
        }
    }
    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: 6 / 6