Submission #1266851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266851		dima2101	Maze (JOI23_ho_t3)	C++20	100 / 100	1953 ms	1135124 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>


struct DSU{
    int n;
    std::vector<int> p;
    std::vector<int> sz;
    std::vector<int> right;
    DSU(int n):n(n){
        p.resize(n);
        sz.resize(n);
        right.resize(n);
        for(int i =0 ;i < n;i++){
            p[i] = i;
            sz[i] = 1;
            right[i] = i;
        }
    }
    DSU() = default;

    int pred(int a){
        if(p[a] == a)return a;
        p[a] = pred(p[a]);
        return p[a];
    }
    void mer(int a,int b){
        a = pred(a),b = pred(b);
        if(a == b)return;
        if(sz[a] > sz[b]){
            std::swap(a,b);
        }
        p[a] = b;
        sz[b] += sz[a];
        right[b] = std::max(right[b],right[a]);
    }
};

void del(int x,int y,std::vector<DSU>& hor,
    std::vector<std::vector<bool>>& ban_hor,
    std::vector<std::vector<bool>>& ban_vert,
    std::vector<DSU>& vert,int r,int c){
    // std::cout<<"dsjf"<<std::endl;

    if(x + 1 < r && ban_vert[x + 1][y]){
        vert[y].mer(x,x + 1);
    }
    if(x - 1 >= 0 && ban_vert[x - 1][y]){
        vert[y].mer(x - 1,x);
    }
    if(y + 1 < c && ban_hor[x][y + 1]){
        hor[x].mer(y,y + 1);
    }
    if(y - 1 >= 0 && ban_vert[x][y - 1]){
        hor[x].mer(y - 1,y);
    }
    ban_hor[x][y] = true;
    ban_vert[x][y] = true;
    // std::cout<<"dsjf"<<std::endl;

}

struct Event{
    bool type;
    int ind;
    int l,r;
    Event(bool type,int ind,int l,int r):type(type),ind(ind),l(l),r(r){};
    Event() = default;
};

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int r,c,n;
    std::cin>>r>>c>>n;

    std::pair<int,int> start;
    std::cin>>start.first>>start.second;
    start.first--;
    start.second--;
    std::pair<int,int> stop;
    std::cin>>stop.first>>stop.second;
    stop.first--;
    stop.second--;

    std::vector<std::vector<char>> a(r,std::vector<char>(c));
    for(int  i=0 ;i < r;i++){
        for(int j =0 ;j < c;j++){
            std::cin>>a[i][j];
        }
    }


    std::vector<std::vector<int>> dist(r,std::vector<int>(c,1e8));

    std::vector<DSU> hor(r);
    std::vector<std::vector<bool>> ban_hor(r,std::vector<bool>(c,false));
    for(int i =0 ;i < r;i++){
        hor[i] = DSU(c);
    }
    std::vector<DSU> vert(c);
    std::vector<std::vector<bool>> ban_vert(r,std::vector<bool>(c,false));
    for(int i =0 ;i <c;i++){
        vert[i] = DSU(r);
    }
    // std::cout<<"dhjf"<<std::endl;

    std::deque<std::pair<int,int>> help;
    help.push_front(start);
    dist[start.first][start.second] = 0;
    del(start.first,start.second,hor,ban_hor,ban_vert,vert,r,c);
    while(help.size() > 0){
        auto v = help.front();
        // std::cout<<v.first<<' '<<v.second<<' '<<dist[v.first][v.second]<<std::endl;
        help.pop_front();

        std::vector<int> dx = {0,0,-1,1};
        std::vector<int> dy = {1,-1,0,0};
        for(int i =0 ;i < dx.size();i++){
            if(v.first + dx[i] >= 0 && v.first + dx[i] < r && 
                v.second + dy[i] >=0  && v.second + dy[i] < c && 
                dist[v.first + dx[i]][v.second + dy[i]] > dist[v.first][v.second] && 
                a[v.first + dx[i]][v.second + dy[i]] == '.'){
                    dist[v.first + dx[i]][v.second + dy[i]] = dist[v.first][v.second];
                    del(v.first + dx[i],v.second + dy[i],hor,ban_hor,ban_vert,vert,r,c);
                    help.push_front({v.first + dx[i],v.second + dy[i]});
            }
        }
        // std::cout<<"djhfs;jlfj"<<std::endl;

        int abs_x = std::abs(v.first - stop.first);
        int abs_y = std::abs(v.second - stop.second);
        if(abs_x <= n && abs_y <= n && abs_x + abs_y != 2 * n){
            if(dist[stop.first][stop.second] > dist[v.first][v.second] + 1){
                // std::cout<<dist[v.first][v.second] + 1<<std::endl;
                dist[stop.first][stop.second] = dist[v.first][v.second] + 1;
                del(stop.first,
                    stop.second,hor,ban_hor,ban_vert,vert,r,c);
                
            }
        }


        dx = {v.first - n + 1,v.first + n - 1,v.first - n + 1,v.first + n - 1};
        dy = {v.second - n + 1,v.second - n + 1,v.second + n - 1,v.second + n - 1};
        for(int i = 0 ;i < dx.size();i++){
            if(dx[i] >= 0 && dx[i] < r && dy[i] >=0 && dy[i] < c){
                if(dist[dx[i]][dy[i]] > dist[v.first][v.second] + 1){
                    dist[dx[i]][dy[i]] = dist[v.first][v.second] + 1;
                    del(dx[i],dy[i],hor,ban_hor,ban_vert,vert,r,c);
                    help.push_back({dx[i],dy[i]});
                }
            }
        }



        std::vector<Event> all;
        if(v.second + n < c){
            all.push_back(Event(0,v.second + n,std::max(0,v.first - n + 1),
            std::min(r - 1,v.first + n - 1)));
        }
        if(v.second - n >= 0){
            all.push_back(Event(0,v.second - n,
                std::max(0,v.first - n + 1),std::min(r - 1,v.first + n - 1)));
        }
        if(v.first + n < r){
            all.push_back(Event(1,v.first + n,std::max(0,v.second - n + 1),std::min(c - 1,v.second + n - 1)));
        }
        if(v.first - n >= 0){
            all.push_back(Event(1,v.first - n,std::max(0,v.second - n + 1),std::min(c - 1,v.second + n - 1)));
        }


        

        for(auto now:all){
            // std::cout<<"aaa"<<std::endl;

            // std::cout<<now.ind<<' '<<now.type<<' '<<now.l<<' '<<now.r<<std::endl;
            if(now.type == 0){
                do{
                    // std::cout<<"aaa"<<std::endl;

                    int tmp = -1;
                    if(!ban_vert[now.l][now.ind]){
                        tmp = now.l;
                    }else{
                        tmp = vert[now.ind].right[vert[now.ind].pred(now.l)];
                        tmp++;
                    }
                    // std::cout<<tmp<<std::endl;
                    // std::cout<<tmp.left<<' '<<tmp.max<<' '<<vert[now.ind].query(0,0,r,tmp.left,tmp.left + 1).max<<std::endl;
                    if(tmp > now.r)break;
                    if(dist[tmp][now.ind] > dist[v.first][v.second] + 1){
                        dist[tmp][now.ind] = dist[v.first][v.second] + 1;
                        help.push_back({tmp,now.ind});
                    }

                    del(tmp,now.ind,hor,ban_hor,ban_vert,vert,r,c);
                    
                    // std::cout<<tmp.left<<' '<<tmp.max<<' '<<vert[now.ind].query(0,0,r,now.l,now.r + 1).max<<std::endl;

                    // exit(0);
                }while(true);
            }else{
                do{
                    // std::cout<<now.l<<' '<<now.r<<' '<<now.type<<' '<<' '<<now.ind<<std::endl;
                    int tmp = -1;
                    if(!ban_hor[now.ind][now.l]){
                        tmp = now.l;
                    }else{
                        tmp = hor[now.ind].right[hor[now.ind].pred(now.l)];
                        // std::cout<<tmp<<std::endl;
                        tmp++;
                    }
                    // std::cout<<tmp<<' '<<hor[now.ind].right[hor[now.ind].pred(now.l)]<<' '<<!ban_hor[now.ind][now.l]<<std::endl;
                    if(tmp > now.r)break;
                    if(dist[now.ind][tmp] > dist[v.first][v.second] + 1){
                        dist[now.ind][tmp] = dist[v.first][v.second] + 1;
                        help.push_back({now.ind,tmp});
                    }
                    del(now.ind,tmp,hor,ban_hor,ban_vert,vert,r,c);
                }while(true);
            }
        }
        // std::cout<<"djf"<<std::endl;

    }
    // for(int i=0;i < r;i++){
    //     for(int j =0 ;j < c;j++){
    //         std::cout<<dist[i][j]<<' ';
    //     }
    //     std::cout<<std::endl;
    // }
    std::cout<<dist[stop.first][stop.second];
}

• 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