Submission #935844

#	Time	Username	Problem	Language	Result	Execution time	Memory
935844		anton	Maze (JOI23_ho_t3)	C++17	67 / 100	2066 ms	73624 KiB

Main

    #include<bits/stdc++.h>
     
     
    using namespace std;
    #define int long long
    #define pii pair<int, int>
     
    int R, C;
    int N;
     
    pii debut;
    pii fin;
     
    vector<vector<char>> maze;
    vector<vector<int>> vis;
     
     
    vector<vector<int>> oc;
    vector<vector<int>> v_s;
     
    pii delta[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
     
    bool is_valid(pii pos){
        if(pos.first>=R || pos.first< 0){
            return false;
        }
        if(pos.second>=C || pos.second<0){
            return false;
        }
        return true;
    }
     
    vector<pii> get_free(pii pos){
        vector<pii> res;
        for(auto d: delta){
            pii c= {pos.first+d.first, pos.second+d.second};
            if(is_valid(c) && maze[c.first][c.second] != '#'){
                res.push_back(c);
            }
        }
        return res;
    }
     
    vector<pii> get_paid(pii pos){
        vector<pii> res;
     
        
        pii c= fin;
        if(is_valid(c)){
            if(abs(c.first-pos.first)<=N && abs(c.second-pos.second)<=N){
                if(abs(c.first-pos.first)<N || abs(c.second-pos.second)<N){
                    res.push_back(c);
                }
            }
        }
        
     
        for(int i= -N; i<=N; i+=2*N){
            for(int j = -(N-1); j<=N-1; j++){
                pii c = {pos.first+i, pos.second+j};
                if(is_valid(c)){
                    res.push_back(c);
                }
            }
        }
     
        for(int i= -N; i<=N; i+=2*N){
            for(int j = -(N-1); j<=N-1; j++){
                pii c = {pos.first+j, pos.second+i};
                if(is_valid(c)){
                    res.push_back(c);
                }
            }
        }
        return res;
    }
     
     
    void display(){
        for(int i = 0; i<R; i++){
            for(int j = 0; j<C; j++){
                if(maze[i][j]=='.'){
                    if(vis[i][j]){
                        cout<<'o';
                    }
                    else{
                        cout<<'.';
                    }
                }
                else{
                    if(vis[i][j]){
                        cout<<'O';
                    }
                    else{
                        cout<<'#';
                    }
                }
            }
            cout<<endl;
        }
        cout<<endl;
    }
    int BFS(){
        deque<pair<pii, int>> dq;
        dq.push_back({debut, 0});
        vis[debut.first][debut.second] = 0;
     
        
        while(dq.size()>0){
            //display();
            auto cur= dq.front();
            dq.pop_front();
            pii cur_pos =cur.first;
     
            int dist = cur.second;
            if(dist!= vis[cur_pos.first][cur_pos.second]){
                continue;
            }
     
            //cout<<cur_pos.first<<" "<<cur_pos.second<<" "<<dist<<endl;
            //cout<<dist<<endl;
     
            if(cur_pos == fin){
                return dist;
            }
            
            for(auto e: get_free(cur_pos)){
                if(vis[e.first][e.second] > dist){
                    vis[e.first][e.second] = dist;
                    dq.push_front({e, dist});
                }
            }
     
            for(auto e: get_paid(cur_pos)){
                if(vis[e.first][e.second]>dist+1){
                    vis[e.first][e.second] = dist+1;
                    dq.push_back({e, dist+1});
                }
            }
        }
        return 1e9;
     
    }
    void BFS2(int cur){
        deque<pair<pii, int>> dq;
        for(int i = 0; i<R; i++){
            for(int j = 0; j<C; j++){
                if(vis[i][j]==cur+1){
                    dq.push_back({{i, j}, vis[i][j]});
                }
            }
        }
     
        
        while(dq.size()>0){
            //display();
            auto cur= dq.front();
            dq.pop_front();
            pii cur_pos =cur.first;
     
     
            int dist = cur.second;        
     
            if(dist!= vis[cur_pos.first][cur_pos.second]){
                continue;
            }
            
            for(auto e: get_free(cur_pos)){
                if(vis[e.first][e.second] > dist){
                    vis[e.first][e.second] = dist;
                    dq.push_front({e, dist});
                }
            }
        }
    }
     
     
    void spread(int cur){
        for(int j = 0; j<C; j++){
            for(int i = 0; i<R; i++){
                v_s[i+1][j] = v_s[i][j] ;
                if(vis[i][j]==cur){
                    v_s[i+1][j] ++;
                }
            }
        }
     
        for(int i = 0; i<R; i++){
            int s= 0;
            for(int j = 0; j<C; j++){
                if(j == 0){
                    for(int k = 0; k<=N; k++){
                        //cout<<j+k<<endl;
                        s+= v_s[min(R, i+N+1)][j+k]-v_s[max(i-(N), 0LL)][j+k];
                    }
                }
     
                oc[i][j] = s ;
                for(int di = -N; di<=N; di+=2*N){
                    for(int dj = -N; dj<=N; dj+=2*N){
                        if(is_valid({i+di, j+dj})){
                            oc[i][j]-=(v_s[i+di+1][j+dj]-v_s[i+di][j+dj]);
                        }
                    }
                }
                if(j-(N)>=0){
                    s-=v_s[min(R, i+N+1)][j-(N)]-v_s[max(i-(N), 0LL)][j-(N)];
                }
                if(j+N+1<C){
                    s+=v_s[min(R, i+N+1)][j+N+1]-v_s[max(i-(N), 0LL)][j+N+1];
                }
            }
        }
     
        for(int i = 0; i<R; i++){
            for(int j = 0; j<C; j++){
                if(oc[i][j]>0 && vis[i][j] == 1e9){
                    vis[i][j] = cur+1;
                }
            }
        }
        BFS2(cur);
    }
     
    signed main(){
        cin>>R>>C;
        cin>>N;
     
        maze.resize(R, vector<char> (C));
        vis.resize(R, vector<int>(C, 1e9));
        oc.resize(R, vector<int>(C));
        v_s.resize(R+1, vector<int>(C, 0));
     
        cin>>debut.first>>debut.second;
        debut.first--;
        debut.second--;
        cin>>fin.first>>fin.second;
        fin.first--;
        fin.second--;
     
        
        for(int i = 0; i<R; i++){
            for(int j = 0; j<C; j++){
                cin>>maze[i][j];
            }
        }
     
        if(N<200){
            cout<<BFS()<<endl;
        }
        else{
            
            vis[debut.first][debut.second] = 0;
            BFS2(-1);
            int c= 0;
            while(vis[fin.first][fin.second] == 1e9){
                spread(c);
                c++;
            }
            cout<<vis[fin.first][fin.second]<<endl;
        }
     
     
    }

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