제출 #1188144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188144		user736482	Maze (JOI23_ho_t3)	C++20	0 / 100	930 ms	2162688 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;
stack<ll>g2[6000000];
vector<ll>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){

            g3[i].pb(i-r);
       // }
       // if(i+r<r*c){

            g3[i].pb(i+r);
        //}
        if(i%r<r-1){

            g3[i].pb(i+1);
            g2[i].push(i-r+1);
            g2[i].push(i+r+1);
        }
        if(i%r){

            g3[i].pb(i-1);
            g2[i].push(i-r-1);
            g2[i].push(i+r-1);
        }

    }
    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){
            while(g2[pom.ss].size()){
                pq.pb({pom.ff+1,g2[pom.ss].top()});g2[pom.ss].pop();
            }
        }

            
        if(pomm%n==0 && co[pom.ss])
            for(ll i : g3[pom.ss]){
                pq.push_front({pom.ff,i});
            }
        
        else
        for(ll i : g3[pom.ss]){
            pq.pb({pom.ff+1,i});
        
        }
    }
    cout<<(dst[t]+n-1)/n;
    return 0;
}

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