Submission #1105521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105521		clams1606	Maze (JOI23_ho_t3)	C++14	35 / 100	120 ms	60156 KiB

Main

#include <bits/stdc++.h>

#define _files
#define _multitest
#define _Debug_

using namespace std;

void just_do_it();

int main() {
    #define task ""
    #ifdef _files_
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    #endif
    #ifdef _Debug
        ios_base::sync_with_stdio(0);
    #endif
    cin.tie(0);
    just_do_it();
    return 0;
}

#define __builtin_popcount __builtin_popcountll
#define BIT(x, i) (((x)>> (i))& (1LL))
#define MASK(x) (1LL<< (x))
#define MOD 1000000007
#define ll long long

const int maxm= (int)1e6, maxn= (int)1e5, maxb= (int)1e3;

ll INF= (ll)1e18;

const int dx[]= {-1, 1,  0, 0};
const int dy[]= { 0, 0, -1, 1};

struct DSU{
    DSU(){}
    vector<int> f;
    DSU(int n){
        f.resize(n+ 1);
        iota(f.begin(), f.end(), 0);
    }
    int lab(int u){
        while(u!= f[u]){
            u= f[u]= f[f[u]];
        }
        return u;
    }
    void mer(int u, int v){
        u= lab(u);
        v= lab(v);
        if(u!= v){
            f[v]= u;
        }
    }
};

struct state{
    state(){}
    int t, x, y, ken;
    state(int _t, int _x, int _y){
        t= _t;
        x= _x;
        y= _y;
    }
};



vector<vector<char> > a;
vector<vector<bool> > vis;
vector<DSU> nxtr, nxtc;
pair<int, int> sta, en;
int r, c, n;
deque<state> st;

bool ok(int pr, int pc){
        return ((0< pr)&& (pr<= r)&& (0< pc)&& (pc<= c)&& (a[pr][pc]== '.'));
}

void input(){
    cin>> r>> c>> n>> sta.first>> sta.second>> en.first>> en.second;
    a.resize(r+ 3, vector<char> (c+ 3));
    vis.resize(r+ 3, vector<bool> (c+ 3));
    nxtr.resize(c+ 3, DSU(r+ 3));
    nxtc.resize(r+ 2, DSU(c+ 3));
    for(int i= 1; i<= r; i++){
        for(int j= 1; j<= c; j++){
            cin>> a[i][j];
        }
    }
}

void prepare(){

}

void solve(){
    st.push_back(state(0, sta.first, sta.second));
    while(st.size()){
        int t= st.front().t, pr= st.front().x, pc= st.front().y;st.pop_front();

        if((pr== en.first)&& (pc== en.second)){
            cout<< t;
            return;
        }
        if(vis[pr][pc]) continue;
        else vis[pr][pc]= true;
        for(int k= 0; k< 4; k++){
            int nr= pr+ dx[k], nc= pc+ dy[k];
            if(ok(nr, nc)&& (vis[nr][nc]== false)){
                st.push_front(state(t, nr, nc));
            }
        }
        int mnr= max(pr- n+ 1, 1), mxr= min(pr+ n- 1, r), mnc= max(pc- n, 1), mxc= min(pc+ n, c);
        for(int i= nxtr[mnc].lab(mnr); i<= mxr; i= nxtr[mnc].lab(i+ 1)){
            for(int j= nxtc[i].lab(mnc); j<= mxc; j= nxtc[i].lab(j+ 1)){
                st.push_back(state(t+ 1, i, j));
                nxtc[i].mer(j+ 1, j);
            }
            nxtr[mnc].mer(i+ 1, i);
        }
        mnr--;
        mxr++;
        mnc++;
        mxc--;
        if(mnr> 0){
            for(int j= nxtc[mnr].lab(mnc); j<= mxc; j= nxtc[mnr].lab(j+ 1)){
                st.push_back(state(t+ 1, mnr, j));
                nxtc[mnr].mer(j+ 1, j);
            }
        }
        if(mxr<= r){
            for(int j= nxtc[mxr].lab(mnc); j<= mxc; j= nxtc[mxr].lab(j+ 1)){
                st.push_back(state(t+ 1, mxr, j));
                nxtc[mxr].mer(j+ 1, j);
            }
        }
    }
}

void printans(){

}

void reset(){

}

void test(){
    input();
    prepare();
    solve();
    printans();
    reset();
}

void just_do_it() {
    int nTest= 1;
    #ifdef _multitest_
        cin>>nTest;
    #endif
    for (int it= 1; it <= nTest; it++) {
        test();
    }
}

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