Submission #1188099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188099		user736482	Maze (JOI23_ho_t3)	C++20	94 / 100	2141 ms	1670652 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[10000000],g2[10000000],g3[10000000];
bool co[10000000];
ll dst[10000000];
bool odw[10000000];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>c>>r>>n;
    cin>>b>>a;
    a--;b--;
    s=r*b+a;
    cin>>b>>a;
    a--;b--;
    t=r*b+a;
    for(ll i=0;i<r*c;i++){
        char ch;
        cin>>ch;
        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);
        }
        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});
            }
        }
        else{
            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