Submission #1151068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151068		AlperenT_	Maze (JOI23_ho_t3)	C++20	100 / 100	1087 ms	569716 KiB

Main

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define int long long 
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e6+20 , maxm = 2e4 + 220, sq = 500 , inf = 1e18+10 , mod =998244353 ; 
int r , c , n ;
bool mark[maxn] ;
char a[maxn] , ok[maxn] ;
vector <int> vec[maxn] , vec2[maxn] ;
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , -1 , 1} ;
int f(int i ,int j){
    return (i-1)*c + j-1 ;
}
pii g(int x){
    return {x/c +1, x%c+1} ;
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> r >> c >> n ;
    int a1 , a2 , b1 , b2 ;
    cin >> a1 >> a2 ;
    cin>> b1 >> b2 ;
    rep(i ,1, r){
        rep(j ,1 ,c){
            cin >> a[f(i,j)];
        }
    }
    vector <int> nw ;
    nw.pb(f(a1,a2)); 
    rep(sp , 0 , r*c){
        queue <int> q ;
        for(int x : nw){
            q.push(x) ;
            mark[x] = 1; 
        }
        while(sz(q)){
            int v = q.front() ;q.pop() ;
            int vi = g(v).F , vj = g(v).S ;
            rep(i , 0 , 3){
                int ui = vi+dx[i] , uj = vj+dy[i] ;
                if(ui <= 0 || ui > r || uj <= 0 || uj > c || a[f(ui , uj)] == '#' || mark[f(ui , uj)] == 1){
                    continue ; 
                }
                mark[f(ui , uj)] = 1; 
                nw.pb(f(ui, uj));
                q.push(f(ui,uj));
            }
        }
        // for(int x : nw){
        //     cout << x << " " ;
        // }
        // cout << "\n"; 
        vector <int> nw2 , ro ;
        if(mark[f(b1,b2)] == 1){
            cout << sp << "\n";
            exit(0) ;
        }
        for(int v : nw){
            int vi = g(v).F , vj = g(v).S ;
            rep(j , 0 , min(vi-1,n-1)){
                if(j != 0 && mark[f(vi-j , vj)]==1)break ;
                vec[vi-j].pb(vj) ;
                ro.pb(vi-j);
            }
            if(vi-n >= 1){
                vec2[vi-n].pb(vj) ;
                ro.pb(vi-n) ;
            }
            rep(j , 1 , min(r-vi , n-1)){
                if(j!=0  && mark[f(vi+j , vj)] == 1)break ;
                vec[vi+j].pb(vj) ;
                ro.pb(vi+j) ;
            }
            if(vi+n <= r){
                vec2[vi+n].pb(vj) ; 
                ro.pb(vi+n) ;
            }
        }
        vector <int> rr ; 
        for(int x : ro){
            if(ok[x] == 0){
                rr.pb(x);
                ok[x] = 1;
            }
        }
        sort(all(rr));
        for(int x : rr)ok[x] =0 ; 
        for(int x : rr){
            sort(all(vec[x])) ;
            sort(all(vec2[x])) ;
            rep(i  , 0 ,sz(vec[x])-1){
                int nx;
                if(i == sz(vec[x])-1)nx = c+1 ;
                else nx = vec[x][i+1] ;
                int z = vec[x][i] ;
                rep(j , z , z+n){
                    if(j >= nx)break ;
                    if(j != z && mark[f(x , j)] == 1)break ;
                    if(mark[f(x,j)] == 0){
                        nw2.pb(f(x,j)) ;
       //                 cout << x<<" " << j << z  << "<1--\n"; 
                    }
                }
            }
            rep(i  , 0 ,sz(vec[x])-1){
                int ls;
                if(i == 0)ls = 0 ;
                else ls = vec[x][i-1] ;
                int z = vec[x][i] ;
                per(j , z , z-n){
                    if(j <= ls)break ;
                    if(j != z && mark[f(x , j)] == 1)break ;
                    if(mark[f(x,j)] == 0){
                        nw2.pb(f(x,j)) ;
        //                cout << x<<" " << j << "<1--\n"; 
                    }
                }
            }
            rep(i  , 0 ,sz(vec2[x])-1){
                int nx;
                if(i == sz(vec2[x])-1)nx = c+1 ;
                else nx = vec2[x][i+1] ;
                int z = vec2[x][i] ;
                rep(j , z , z+n-1){
                    if(j >= nx)break ;
                    if(j != z && mark[f(x , j)] == 1)break ;
                    if(mark[f(x,j)] == 0){
                        nw2.pb(f(x,j)) ;
                 //       cout << x<<" " << j << "<1--\n"; 
                    }
                }
            }
            rep(i  , 0 ,sz(vec2[x])-1){
                int ls;
                if(i == 0)ls = 0 ;
                else ls = vec2[x][i-1] ;
                int z = vec2[x][i] ;
                per(j , z , z-n+1){
                    if(j <= ls)break ;
                    if(j != z && mark[f(x , j)] == 1)break ;
                    if(mark[f(x,j)] == 0){
                        nw2.pb(f(x,j)) ;
              //          cout << x<<" " << j << "<1--\n"; 
                    }
                }
            }
        }
        nw.clear() ;
        for(int x : nw2){
            if(mark[x] == 0){
                mark[x] =1 ;
                nw.pb(x); 
            }
        }
        for(int x : rr){
            vec[x].clear() ;   
            vec2[x].clear() ;
        }
    }

}
/*
 
*/

• 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