Submission #935830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
935830	2024-02-29T15:45:11 Z	anton	Maze (JOI23_ho_t3)	C++17	16 / 100	211 ms	75036 KB

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;
}

void BFS(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;
            }
        }
    }
    BFS(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];
        }
    }

    

    vis[debut.first][debut.second] = 0;


    BFS(-1);
    
    int c= 0;
    while(vis[fin.first][fin.second] == 1e9 && c<=10){
        spread(c);
        c++;
    }
    cout<<vis[fin.first][fin.second]<<endl;

}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 19.0

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

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	8 ms	1372 KB	Output is correct
26	Correct	7 ms	2060 KB	Output is correct
27	Correct	8 ms	2652 KB	Output is correct
28	Correct	8 ms	2648 KB	Output is correct
29	Correct	11 ms	3416 KB	Output is correct
30	Correct	5 ms	3160 KB	Output is correct
31	Correct	8 ms	1884 KB	Output is correct
32	Correct	5 ms	1940 KB	Output is correct
33	Correct	10 ms	1884 KB	Output is correct
34	Correct	14 ms	3676 KB	Output is correct
35	Correct	22 ms	5980 KB	Output is correct
36	Correct	27 ms	6012 KB	Output is correct
37	Correct	24 ms	7772 KB	Output is correct
38	Correct	15 ms	7740 KB	Output is correct
39	Correct	60 ms	12528 KB	Output is correct
40	Correct	144 ms	35664 KB	Output is correct
41	Correct	211 ms	55568 KB	Output is correct
42	Correct	210 ms	55348 KB	Output is correct
43	Correct	203 ms	74844 KB	Output is correct
44	Correct	142 ms	75036 KB	Output is correct
45	Correct	155 ms	40348 KB	Output is correct
46	Correct	159 ms	40272 KB	Output is correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 6.0

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

Submission #935830

Compilation message