oj.uz

Submission #1105522

# Submission time Handle Problem Language Result Execution time Memory
1105522 2024-10-26T16:16:29 Z clams1606 Maze (JOI23_ho_t3) C++14
0 / 100
 10 ms 4688 KB 
#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(){
    vis[sta.first][sta.second]== true;
    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;
        }
        for(int k= 0; k< 4; k++){
            int nr= pr+ dx[k], nc= pc+ dy[k];
            if(ok(nr, nc)&& (vis[nr][nc]== false)){
                vis[nr][nc]= true;
                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)){
                if(vis[i][j]== false){
                    vis[i][j]= true;
                    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)){
                if(vis[mnr][j]== false){
                    vis[mnr][j]= true;
                    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)){
                if(vis[mxr][j]== false){
                    vis[mxr][j]= true;
                    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();
    }
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:101:31: warning: value computed is not used [-Wunused-value]
  101 |     vis[sta.first][sta.second]== true;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 4 ms 848 KB Output is correct
20 Correct 5 ms 3664 KB Output is correct
21 Correct 4 ms 1540 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 4 ms 848 KB Output is correct
24 Correct 7 ms 4688 KB Output is correct
25 Correct 10 ms 4688 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 2 ms 848 KB Output is correct
28 Incorrect 3 ms 1216 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 4 ms 848 KB Output is correct
20 Correct 5 ms 3664 KB Output is correct
21 Correct 4 ms 1540 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 4 ms 848 KB Output is correct
24 Correct 7 ms 4688 KB Output is correct
25 Correct 10 ms 4688 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 2 ms 848 KB Output is correct
28 Incorrect 3 ms 1216 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 4 ms 848 KB Output is correct
20 Correct 5 ms 3664 KB Output is correct
21 Correct 4 ms 1540 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 4 ms 848 KB Output is correct
24 Correct 7 ms 4688 KB Output is correct
25 Correct 10 ms 4688 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 2 ms 848 KB Output is correct
28 Incorrect 3 ms 1216 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 4 ms 848 KB Output is correct
20 Correct 5 ms 3664 KB Output is correct
21 Correct 4 ms 1540 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 4 ms 848 KB Output is correct
24 Correct 7 ms 4688 KB Output is correct
25 Correct 10 ms 4688 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 2 ms 848 KB Output is correct
28 Incorrect 3 ms 1216 KB Output isn't correct
29 Halted 0 ms 0 KB -