oj.uz

Submission #986025

# Submission time Handle Problem Language Result Execution time Memory
986025 2024-05-19T16:28:42 Z VinhLuu Maze (JOI23_ho_t3) C++17
0 / 100
 2000 ms 613228 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<ll,int,int> tp;
const int N = 6e6 + 5;
const ll oo = 1e14 + 1;
const int mod = 1e9 + 7;
//const ll oo = 5e18;

const int ha[4] = {1, -1, 0, 0};
const int co[4] = {0, 0, 1, -1};
const int tx[4] = {1, 1, -1, -1};
const int ty[4] = {1, -1, -1, 1};

int m, n, k, xt, yt, xs, ys;

ll ans;

vector<ll> f[N];
vector<int> a[N], ph[N], pc[N];
deque<tp> q;

bool kt(int x,int y){
    return x >= 1 && x <= m && y >= 1 && y <= n;
}

int row(int u,int v){
    return (ph[u][v] == v ? v : ph[u][v] = row(u, ph[u][v]));
}

int col(int u,int v){
    return (pc[u][v] == u ? u : pc[u][v] = col(pc[u][v], v));
}

void conduct(ll val,int x,int y){
    int l = max(1, x - k + 1), r = min(m, x + k - 1), pl = max(1, y - k + 1), pr = min(n, y + k - 1);
    if(xt >= l && xt <= r && yt >= pl && yt <= pr) ans = min(ans, val + 1);
    if(l - 1 >= 1){
        int lx = l - 1, g = pr;
        while(ph[lx][g] >= pl){
            g = ph[lx][g];
            if(f[lx][g] > val + 1 + a[lx][g]) f[lx][g] = val + 1 + a[lx][g], q.push_back({f[lx][g], lx, g});
            if(!ph[lx][g]) break;
            ph[lx][g]--;
            ph[lx][g] = row(lx, ph[lx][g]);
        }
    }
    if(r + 1 <= m){
        int lx = r + 1, g = pr;
        while(ph[lx][g] >= pl){
            g = ph[lx][g];
            if(f[lx][g] > val + 1 + a[lx][g]) f[lx][g] = val + 1 + a[lx][g], q.push_back({f[lx][g], lx, g});
            if(!ph[lx][g]) break;
            ph[lx][g]--;
            ph[lx][g] = row(lx, ph[lx][g]);
        }
    }
    if(pl - 1 >= 1){
        int g = r, ly = pl - 1;
        while(pc[g][ly] >= l){
            g = pc[g][ly];
            if(f[g][ly] > val + 1 + a[g][ly]) f[g][ly] = val + 1 + a[g][ly], q.push_back({f[g][ly], g, ly});
            if(!pc[g][ly]) break;
            pc[g][ly]--;
            pc[g][ly] = col(pc[g][ly], ly);
        }
    }

    if(pr + 1 <= n){
        int g = r, ly = pr + 1;
        while(pc[g][ly] >= l){
            g = pc[g][ly];
            if(f[g][ly] > val + 1 + a[g][ly]) f[g][ly] = val + 1 + a[g][ly], q.push_back({f[g][ly], g, ly});
            if(!pc[g][ly]) break;
            pc[g][ly]--;
            pc[g][ly] = col(pc[g][ly], ly);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> m >> n >> k;
    cin >> xs >> ys >> xt >> yt;
    for(int i = 1; i <= m; i ++){
        string s; cin >> s;
        f[i].pb(oo);
        a[i].pb(0);
        ph[i].pb(0);
        pc[i].pb(0);
        for(int j = 0; j < n; j ++){
            f[i].pb(oo);
            pc[i].pb(0);
            ph[i].pb(j + 1);
            if(s[j] == '.') a[i].pb(0);
            else a[i].pb(1);
        }
        f[i].pb(oo);
        a[i].pb(0);
        ph[i].pb(0);
        pc[i].pb(0);
    }
    for(int i = 1; i <= n + 1; i ++) pc[0].pb(0);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            pc[j][i] = j;
        }
    }

    f[xs][ys] = 0;
    q.push_back({0, xs, ys});
    ans = oo;
    while(!q.empty()){
        ll val;
        int px, py; tie(val, px, py) = q.front();
        q.pop_front();
        if(val > f[px][py]) continue;
        if(px == xt && py == yt) ans = min(ans, f[px][py]);

        conduct(val, px, py);

        for(int d = 0; d < 4; d ++){
            int x = px + ha[d];
            int y = py + co[d];
            if(!kt(x, y) || f[x][y] <= f[px][py] + a[x][y]) continue;
            f[x][y] = f[px][py] + a[x][y];
            if(a[x][y]) q.push_back({f[x][y], x, y});
            else q.push_front({f[x][y], x, y});
            if(ph[x][y]){
                ph[x][y]--;
                ph[x][y] = row(x, ph[x][y]);
            }
            if(pc[x][y]){
                pc[x][y]--;
                pc[x][y] = col(pc[x][y], y);
            }

            conduct(val, x, y);

        }
    }
    cout << min(ans, f[xt][yt]);
}

/*
6 6 3
5 4
2 1
###.#.
#..#..
...###
###.##
..####
#.#...
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 563800 KB Output is correct
2 Correct 202 ms 563784 KB Output is correct
3 Correct 223 ms 564056 KB Output is correct
4 Correct 203 ms 564100 KB Output is correct
5 Correct 217 ms 564056 KB Output is correct
6 Correct 201 ms 564072 KB Output is correct
7 Correct 261 ms 564056 KB Output is correct
8 Correct 203 ms 564052 KB Output is correct
9 Correct 275 ms 564164 KB Output is correct
10 Correct 201 ms 563792 KB Output is correct
11 Correct 203 ms 563796 KB Output is correct
12 Correct 206 ms 564048 KB Output is correct
13 Correct 205 ms 563796 KB Output is correct
14 Correct 201 ms 563796 KB Output is correct
15 Correct 214 ms 563984 KB Output is correct
16 Correct 235 ms 564048 KB Output is correct
17 Correct 218 ms 564084 KB Output is correct
18 Correct 219 ms 564288 KB Output is correct
19 Correct 245 ms 565324 KB Output is correct
20 Correct 216 ms 565676 KB Output is correct
21 Correct 220 ms 566356 KB Output is correct
22 Correct 241 ms 565332 KB Output is correct
23 Correct 234 ms 565588 KB Output is correct
24 Correct 223 ms 565968 KB Output is correct
25 Correct 219 ms 565956 KB Output is correct
26 Correct 224 ms 565844 KB Output is correct
27 Correct 230 ms 565332 KB Output is correct
28 Correct 218 ms 565332 KB Output is correct
29 Correct 338 ms 568468 KB Output is correct
30 Correct 652 ms 565712 KB Output is correct
31 Correct 230 ms 571732 KB Output is correct
32 Correct 286 ms 568148 KB Output is correct
33 Correct 261 ms 567972 KB Output is correct
34 Correct 228 ms 569020 KB Output is correct
35 Correct 229 ms 569060 KB Output is correct
36 Correct 248 ms 568620 KB Output is correct
37 Correct 268 ms 568400 KB Output is correct
38 Correct 234 ms 568204 KB Output is correct
39 Execution timed out 2047 ms 613228 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 564036 KB Output is correct
2 Correct 235 ms 563960 KB Output is correct
3 Correct 229 ms 563808 KB Output is correct
4 Correct 221 ms 563980 KB Output is correct
5 Correct 222 ms 564292 KB Output is correct
6 Correct 220 ms 563936 KB Output is correct
7 Correct 220 ms 564048 KB Output is correct
8 Incorrect 217 ms 563932 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 563796 KB Output is correct
2 Correct 214 ms 564036 KB Output is correct
3 Correct 215 ms 564036 KB Output is correct
4 Correct 218 ms 563796 KB Output is correct
5 Correct 220 ms 563856 KB Output is correct
6 Correct 215 ms 564036 KB Output is correct
7 Correct 220 ms 564052 KB Output is correct
8 Correct 217 ms 564024 KB Output is correct
9 Correct 214 ms 564048 KB Output is correct
10 Correct 216 ms 564052 KB Output is correct
11 Correct 214 ms 564016 KB Output is correct
12 Correct 215 ms 564048 KB Output is correct
13 Correct 217 ms 563956 KB Output is correct
14 Correct 223 ms 564168 KB Output is correct
15 Correct 217 ms 563796 KB Output is correct
16 Correct 216 ms 564052 KB Output is correct
17 Correct 220 ms 564144 KB Output is correct
18 Correct 216 ms 563792 KB Output is correct
19 Correct 215 ms 563940 KB Output is correct
20 Correct 219 ms 564068 KB Output is correct
21 Incorrect 214 ms 564048 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 564036 KB Output is correct
2 Correct 235 ms 563960 KB Output is correct
3 Correct 229 ms 563808 KB Output is correct
4 Correct 221 ms 563980 KB Output is correct
5 Correct 222 ms 564292 KB Output is correct
6 Correct 220 ms 563936 KB Output is correct
7 Correct 220 ms 564048 KB Output is correct
8 Incorrect 217 ms 563932 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 564036 KB Output is correct
2 Correct 235 ms 563960 KB Output is correct
3 Correct 229 ms 563808 KB Output is correct
4 Correct 221 ms 563980 KB Output is correct
5 Correct 222 ms 564292 KB Output is correct
6 Correct 220 ms 563936 KB Output is correct
7 Correct 220 ms 564048 KB Output is correct
8 Incorrect 217 ms 563932 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 563800 KB Output is correct
2 Correct 202 ms 563784 KB Output is correct
3 Correct 223 ms 564056 KB Output is correct
4 Correct 203 ms 564100 KB Output is correct
5 Correct 217 ms 564056 KB Output is correct
6 Correct 201 ms 564072 KB Output is correct
7 Correct 261 ms 564056 KB Output is correct
8 Correct 203 ms 564052 KB Output is correct
9 Correct 275 ms 564164 KB Output is correct
10 Correct 201 ms 563792 KB Output is correct
11 Correct 203 ms 563796 KB Output is correct
12 Correct 206 ms 564048 KB Output is correct
13 Correct 205 ms 563796 KB Output is correct
14 Correct 201 ms 563796 KB Output is correct
15 Correct 214 ms 563984 KB Output is correct
16 Correct 235 ms 564048 KB Output is correct
17 Correct 218 ms 564084 KB Output is correct
18 Correct 219 ms 564288 KB Output is correct
19 Correct 245 ms 565324 KB Output is correct
20 Correct 216 ms 565676 KB Output is correct
21 Correct 220 ms 566356 KB Output is correct
22 Correct 241 ms 565332 KB Output is correct
23 Correct 234 ms 565588 KB Output is correct
24 Correct 223 ms 565968 KB Output is correct
25 Correct 219 ms 565956 KB Output is correct
26 Correct 224 ms 565844 KB Output is correct
27 Correct 230 ms 565332 KB Output is correct
28 Correct 218 ms 565332 KB Output is correct
29 Correct 338 ms 568468 KB Output is correct
30 Correct 652 ms 565712 KB Output is correct
31 Correct 230 ms 571732 KB Output is correct
32 Correct 286 ms 568148 KB Output is correct
33 Correct 261 ms 567972 KB Output is correct
34 Correct 228 ms 569020 KB Output is correct
35 Correct 229 ms 569060 KB Output is correct
36 Correct 248 ms 568620 KB Output is correct
37 Correct 268 ms 568400 KB Output is correct
38 Correct 234 ms 568204 KB Output is correct
39 Execution timed out 2047 ms 613228 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 563800 KB Output is correct
2 Correct 202 ms 563784 KB Output is correct
3 Correct 223 ms 564056 KB Output is correct
4 Correct 203 ms 564100 KB Output is correct
5 Correct 217 ms 564056 KB Output is correct
6 Correct 201 ms 564072 KB Output is correct
7 Correct 261 ms 564056 KB Output is correct
8 Correct 203 ms 564052 KB Output is correct
9 Correct 275 ms 564164 KB Output is correct
10 Correct 201 ms 563792 KB Output is correct
11 Correct 203 ms 563796 KB Output is correct
12 Correct 206 ms 564048 KB Output is correct
13 Correct 205 ms 563796 KB Output is correct
14 Correct 201 ms 563796 KB Output is correct
15 Correct 214 ms 563984 KB Output is correct
16 Correct 235 ms 564048 KB Output is correct
17 Correct 218 ms 564084 KB Output is correct
18 Correct 219 ms 564288 KB Output is correct
19 Correct 245 ms 565324 KB Output is correct
20 Correct 216 ms 565676 KB Output is correct
21 Correct 220 ms 566356 KB Output is correct
22 Correct 241 ms 565332 KB Output is correct
23 Correct 234 ms 565588 KB Output is correct
24 Correct 223 ms 565968 KB Output is correct
25 Correct 219 ms 565956 KB Output is correct
26 Correct 224 ms 565844 KB Output is correct
27 Correct 230 ms 565332 KB Output is correct
28 Correct 218 ms 565332 KB Output is correct
29 Correct 338 ms 568468 KB Output is correct
30 Correct 652 ms 565712 KB Output is correct
31 Correct 230 ms 571732 KB Output is correct
32 Correct 286 ms 568148 KB Output is correct
33 Correct 261 ms 567972 KB Output is correct
34 Correct 228 ms 569020 KB Output is correct
35 Correct 229 ms 569060 KB Output is correct
36 Correct 248 ms 568620 KB Output is correct
37 Correct 268 ms 568400 KB Output is correct
38 Correct 234 ms 568204 KB Output is correct
39 Execution timed out 2047 ms 613228 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 563800 KB Output is correct
2 Correct 202 ms 563784 KB Output is correct
3 Correct 223 ms 564056 KB Output is correct
4 Correct 203 ms 564100 KB Output is correct
5 Correct 217 ms 564056 KB Output is correct
6 Correct 201 ms 564072 KB Output is correct
7 Correct 261 ms 564056 KB Output is correct
8 Correct 203 ms 564052 KB Output is correct
9 Correct 275 ms 564164 KB Output is correct
10 Correct 201 ms 563792 KB Output is correct
11 Correct 203 ms 563796 KB Output is correct
12 Correct 206 ms 564048 KB Output is correct
13 Correct 205 ms 563796 KB Output is correct
14 Correct 201 ms 563796 KB Output is correct
15 Correct 214 ms 563984 KB Output is correct
16 Correct 235 ms 564048 KB Output is correct
17 Correct 218 ms 564084 KB Output is correct
18 Correct 219 ms 564288 KB Output is correct
19 Correct 245 ms 565324 KB Output is correct
20 Correct 216 ms 565676 KB Output is correct
21 Correct 220 ms 566356 KB Output is correct
22 Correct 241 ms 565332 KB Output is correct
23 Correct 234 ms 565588 KB Output is correct
24 Correct 223 ms 565968 KB Output is correct
25 Correct 219 ms 565956 KB Output is correct
26 Correct 224 ms 565844 KB Output is correct
27 Correct 230 ms 565332 KB Output is correct
28 Correct 218 ms 565332 KB Output is correct
29 Correct 338 ms 568468 KB Output is correct
30 Correct 652 ms 565712 KB Output is correct
31 Correct 230 ms 571732 KB Output is correct
32 Correct 286 ms 568148 KB Output is correct
33 Correct 261 ms 567972 KB Output is correct
34 Correct 228 ms 569020 KB Output is correct
35 Correct 229 ms 569060 KB Output is correct
36 Correct 248 ms 568620 KB Output is correct
37 Correct 268 ms 568400 KB Output is correct
38 Correct 234 ms 568204 KB Output is correct
39 Execution timed out 2047 ms 613228 KB Time limit exceeded
40 Halted 0 ms 0 KB -