Submission #1076889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1076889	2024-08-26T18:01:24 Z	dwuy	Maze (JOI23_ho_t3)	C++14	0 / 100	57 ms	94300 KB

Main

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MX = 3000006;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct vortex{
    int id;
    int d[MX];
    vortex(): id(0) {}

    void push_back(int x){
        id++;
        d[id] = x;
    }

    void pop_back(){
        if(id) id--;
    }

    void clear(){
        id = 0;
    }

    int gx(int i){
        return !i || i > id? -1 : d[i];
    }
};

int n, m, k;
int Sx, Sy, Ex, Ey;
vector<vector<int>> ttr;
vector<vector<int>> ttb;
vector<vector<int>> d;
string a[MX];
queue<pii> Q[2];

void nhap(){
    cin >> n >> m >> k;
    cin >> Sx >> Sy >> Ex >> Ey;
    ttr.assign(n + 5, vector<int>(m + 5, 0));
    ttb.assign(m + 5, vector<int>(n + 5, 0));
    for(int i=1; i<=n; i++){
        cin >> a[i];
        a[i] = ' ' + a[i];
        for(int j=1; j<=m; j++){
            ttr[i][j] = j + 1;
            ttb[j][i] = i + 1;
        }
    }
}

void solve(){
    d.assign(n + 5, vector<int>(m + 5, 1e9));
    d[Sx][Sy] = 0;
    Q[0].push({Sx, Sy});
    for(int f=0; f<n*m; f++){
        int c = f&1;
        vector<pii> vt;
        while(Q[c].size()){
            int x, y;
            tie(x, y) = Q[c].front();
            vt.push_back({x, y});
            Q[c].pop();
            for(int i=0; i<4; i++){
                int u = x + dx[i];
                int v = y + dy[i];
                if(u < 1 || u > n || v < 1 || v > m || a[u][v] == '#' || d[u][v] <= d[x][y]) continue;
                d[u][v] = d[x][y];
                Q[c].push({u, v});
            }
        }
        for(pii td: vt){
            int x, y;
            tie(x, y) = td;
            vector<int> vert;
            for(int i=max(1, x-k); i<=min(n, x+k);){
                vert.push_back(i);
                vector<int> hori;
                for(int j=max(1, y-k); j<=min(m, y+k);){
                    hori.push_back(j);
                    if((i == x - k || i == x + k) && (j == y - k || j == y + k)){
                        j = ttr[i][j];
                        continue;
                    }
                    if(d[i][j] > d[x][y] + 1){
                        d[i][j] = d[x][y] + 1;
                        Q[c^1].push({i, j});
                    }
                    j = ttr[i][j];
                }
                for(int j: hori) ttr[i][j] = ttr[i][hori.back()];
                i = ttb[y][i];
            }
            for(int i: vert) ttb[y][i] = ttb[y][vert.back()];
        }
    }
    cout << d[Ex][Ey];
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    nhap();
    solve();

    return 0;
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	94292 KB	Output is correct
2	Correct	44 ms	94192 KB	Output is correct
3	Correct	41 ms	94288 KB	Output is correct
4	Correct	44 ms	94288 KB	Output is correct
5	Incorrect	43 ms	94300 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	94288 KB	Output is correct
2	Correct	47 ms	94212 KB	Output is correct
3	Correct	43 ms	94288 KB	Output is correct
4	Correct	52 ms	94292 KB	Output is correct
5	Correct	43 ms	94292 KB	Output is correct
6	Correct	44 ms	94292 KB	Output is correct
7	Correct	41 ms	94288 KB	Output is correct
8	Correct	43 ms	94300 KB	Output is correct
9	Correct	45 ms	94288 KB	Output is correct
10	Incorrect	48 ms	94288 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #3
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	94272 KB	Output is correct
2	Correct	51 ms	94284 KB	Output is correct
3	Correct	42 ms	94288 KB	Output is correct
4	Correct	42 ms	94288 KB	Output is correct
5	Correct	46 ms	94276 KB	Output is correct
6	Correct	46 ms	94264 KB	Output is correct
7	Correct	43 ms	94288 KB	Output is correct
8	Incorrect	44 ms	94284 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	94288 KB	Output is correct
2	Correct	47 ms	94212 KB	Output is correct
3	Correct	43 ms	94288 KB	Output is correct
4	Correct	52 ms	94292 KB	Output is correct
5	Correct	43 ms	94292 KB	Output is correct
6	Correct	44 ms	94292 KB	Output is correct
7	Correct	41 ms	94288 KB	Output is correct
8	Correct	43 ms	94300 KB	Output is correct
9	Correct	45 ms	94288 KB	Output is correct
10	Incorrect	48 ms	94288 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	94288 KB	Output is correct
2	Correct	47 ms	94212 KB	Output is correct
3	Correct	43 ms	94288 KB	Output is correct
4	Correct	52 ms	94292 KB	Output is correct
5	Correct	43 ms	94292 KB	Output is correct
6	Correct	44 ms	94292 KB	Output is correct
7	Correct	41 ms	94288 KB	Output is correct
8	Correct	43 ms	94300 KB	Output is correct
9	Correct	45 ms	94288 KB	Output is correct
10	Incorrect	48 ms	94288 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	94292 KB	Output is correct
2	Correct	44 ms	94192 KB	Output is correct
3	Correct	41 ms	94288 KB	Output is correct
4	Correct	44 ms	94288 KB	Output is correct
5	Incorrect	43 ms	94300 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	94292 KB	Output is correct
2	Correct	44 ms	94192 KB	Output is correct
3	Correct	41 ms	94288 KB	Output is correct
4	Correct	44 ms	94288 KB	Output is correct
5	Incorrect	43 ms	94300 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	94292 KB	Output is correct
2	Correct	44 ms	94192 KB	Output is correct
3	Correct	41 ms	94288 KB	Output is correct
4	Correct	44 ms	94288 KB	Output is correct
5	Incorrect	43 ms	94300 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Submission #1076889

Compilation message