oj.uz

Submission #986017

# Submission time Handle Problem Language Result Execution time Memory
986017 2024-05-19T16:10:43 Z VinhLuu Maze (JOI23_ho_t3) C++17
0 / 100
 360 ms 564208 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;

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

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

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

//    for(int i = 1; i <= m; i ++){
//        for(int j = 1; j <= n; j ++) cout << a[i][j] << " ";
//        cout << "\n";
//    }
    priority_queue<tp, vector<tp>, greater<tp>> q;
    f[xs][ys] = 0;
    q.push({0, xs, ys});
    ll ans = oo;
    while(!q.empty()){
        ll val;
        int px, py; tie(val, px, py) = q.top();
//        int x = q.front().fi;
//        int y = q.front().se;
        q.pop();
        if(val > f[px][py]) continue;
        if(px == xt && py == yt) ans = min(ans, f[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];
            q.push({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);
            }
            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) f[lx][g] = val + 1, q.push({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) f[lx][g] = val + 1, q.push({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) f[g][ly] = val + 1, q.push({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) f[g][ly] = val + 1, q.push({f[g][ly], g, ly});
                    if(!pc[g][ly]) break;
                    pc[g][ly]--;
                    pc[g][ly] = col(pc[g][ly], ly);
                }
            }
        }
    }
    cout << min(ans, f[xt][yt]);
}

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

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 564092 KB Output is correct
2 Correct 204 ms 563824 KB Output is correct
3 Incorrect 258 ms 563972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 563912 KB Output is correct
2 Correct 200 ms 563892 KB Output is correct
3 Correct 202 ms 564032 KB Output is correct
4 Correct 202 ms 563792 KB Output is correct
5 Incorrect 207 ms 564048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 564052 KB Output is correct
2 Correct 204 ms 563796 KB Output is correct
3 Correct 209 ms 563792 KB Output is correct
4 Correct 213 ms 564056 KB Output is correct
5 Correct 204 ms 563792 KB Output is correct
6 Correct 225 ms 564032 KB Output is correct
7 Correct 214 ms 564104 KB Output is correct
8 Correct 204 ms 564076 KB Output is correct
9 Correct 209 ms 563920 KB Output is correct
10 Correct 206 ms 564208 KB Output is correct
11 Correct 205 ms 563892 KB Output is correct
12 Correct 207 ms 564032 KB Output is correct
13 Correct 206 ms 563984 KB Output is correct
14 Correct 206 ms 564052 KB Output is correct
15 Incorrect 204 ms 564032 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 563912 KB Output is correct
2 Correct 200 ms 563892 KB Output is correct
3 Correct 202 ms 564032 KB Output is correct
4 Correct 202 ms 563792 KB Output is correct
5 Incorrect 207 ms 564048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 563912 KB Output is correct
2 Correct 200 ms 563892 KB Output is correct
3 Correct 202 ms 564032 KB Output is correct
4 Correct 202 ms 563792 KB Output is correct
5 Incorrect 207 ms 564048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 564092 KB Output is correct
2 Correct 204 ms 563824 KB Output is correct
3 Incorrect 258 ms 563972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 564092 KB Output is correct
2 Correct 204 ms 563824 KB Output is correct
3 Incorrect 258 ms 563972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 564092 KB Output is correct
2 Correct 204 ms 563824 KB Output is correct
3 Incorrect 258 ms 563972 KB Output isn't correct
4 Halted 0 ms 0 KB -