oj.uz

Submission #738904

# Submission time Handle Problem Language Result Execution time Memory
738904 2023-05-09T15:43:32 Z He_Huanglu Maze (JOI23_ho_t3) C++17
8 / 100
 526 ms 775360 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 6e6 + 3;
int n, m, s, rs, cs, re, ce;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector <int> f[N], a[N], p[2][N], ok[N];
queue <ii> q[2];

int get(int t, int id, int u) {
    return p[t][id][u] == u ? u : p[t][id][u] = get(t, id, p[t][id][u]);
}

void upd(int t, int id, int i, int j, int val) {
    int u = get(t, id, i);
    while (u <= j) {
        if(t) f[id][u] = val;
        else f[u][id] = val;
        u = get(t, id, u + 1);
        p[t][id][i] = u;
    }
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> m >> n >> s >> rs >> cs >> re >> ce;
    for(int i = 1; i <= m; i++) a[i].resize(n + 1), f[i].resize(n + 1), ok[i].resize(n + 1);
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j <= n + 1; j++) p[1][i].push_back(j);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= m + 1; j++) p[0][i].push_back(j);
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            char ch; cin >> ch;
            a[i][j] = (ch == '.' ? 1 : 0);
        }
    }
    q[1].push({rs, cs}); f[rs][cs] = 1;
    while (!q[1].empty() || !q[0].empty()) {
        while (!q[1].empty()) {
            int x, y; tie(x, y) = q[1].front(); q[1].pop();
            q[0].push({x, y});
            if(x == re && y == ce) return cout << f[x][y] - 1 << "\n", 0;
            for(int i = 0; i < 4; i++) {
                int u = x + dx[i], v = y + dy[i];
                if(u && u <= m && v && v <= n && !f[u][v] && a[u][v]) {
                    f[u][v] = f[x][y];
                    q[1].push({u, v});
                }
            }
        }
        while (!q[0].empty()) {
            int x, y; tie(x, y) = q[0].front(); q[0].pop();
            if(s != 1) {
                if(x == rs && y == cs) {
                    int s1 = max(1, x - s), s2 = max(1, y - s);
                    int s3 = min(m, x + s), s4 = min(n, y + s);
                    for(int i = s1; i <= s3; i++) {
                        for(int j = s2; j <= s4; j++) if(!f[i][j]) {
                            f[i][j] = f[x][y] + 1;
                            q[1].push({i, j});
                        }
                    }
                }
                else {
                    for(int i = 0; i < 4; i++) {
                        int u = x + dx[i], v = y + dy[i], val = f[x][y] + 1;
                        if(u && u <= m && v && v <= n && ok[u][v]) {
                            if(i == 0) upd(0, min(n, y + s), max(1, x - s), min(m, x + s), val);
                            if(i == 1) upd(1, min(m, x + s), max(1, y - s), min(n, y + s), val);
                            if(i == 2) upd(0, max(1, y - s), max(1, x - s), min(m, x + s), val);
                            if(i == 3) upd(1, max(1, x - s), max(1, y - s), min(n, y + s), val);
                            break ;
                        }
                    }
                }
                ok[x][y] = 1;
            }
            else {
                for(int i = 0; i < 4; i++) {
                    int u = x + dx[i], v = y + dy[i];
                    if(u && u <= m && v && v <= n && !f[u][v]) {
                        f[u][v] = f[x][y] + 1;
                        q[1].push({u, v});
                    }
                }
            }
        }
    }

}

Compilation message

Main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main () {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 704808 KB Output is correct
2 Correct 331 ms 704768 KB Output is correct
3 Correct 356 ms 704844 KB Output is correct
4 Correct 329 ms 704824 KB Output is correct
5 Correct 331 ms 704784 KB Output is correct
6 Correct 353 ms 704832 KB Output is correct
7 Correct 335 ms 704856 KB Output is correct
8 Correct 393 ms 704856 KB Output is correct
9 Correct 384 ms 704696 KB Output is correct
10 Correct 381 ms 704688 KB Output is correct
11 Correct 352 ms 704696 KB Output is correct
12 Correct 368 ms 704808 KB Output is correct
13 Correct 380 ms 704808 KB Output is correct
14 Correct 355 ms 704912 KB Output is correct
15 Correct 335 ms 704808 KB Output is correct
16 Correct 349 ms 704796 KB Output is correct
17 Correct 335 ms 704876 KB Output is correct
18 Correct 449 ms 704716 KB Output is correct
19 Correct 389 ms 705960 KB Output is correct
20 Correct 366 ms 706948 KB Output is correct
21 Correct 340 ms 706344 KB Output is correct
22 Correct 359 ms 706008 KB Output is correct
23 Correct 333 ms 706000 KB Output is correct
24 Correct 329 ms 707560 KB Output is correct
25 Correct 334 ms 707756 KB Output is correct
26 Correct 322 ms 706016 KB Output is correct
27 Correct 317 ms 705996 KB Output is correct
28 Correct 314 ms 706012 KB Output is correct
29 Correct 353 ms 708096 KB Output is correct
30 Correct 320 ms 706800 KB Output is correct
31 Correct 381 ms 709240 KB Output is correct
32 Correct 350 ms 708172 KB Output is correct
33 Correct 343 ms 708084 KB Output is correct
34 Correct 348 ms 711760 KB Output is correct
35 Correct 356 ms 711860 KB Output is correct
36 Correct 333 ms 708248 KB Output is correct
37 Correct 330 ms 708220 KB Output is correct
38 Correct 331 ms 708168 KB Output is correct
39 Correct 454 ms 742148 KB Output is correct
40 Correct 355 ms 709012 KB Output is correct
41 Correct 341 ms 713416 KB Output is correct
42 Correct 346 ms 710008 KB Output is correct
43 Correct 348 ms 712512 KB Output is correct
44 Correct 364 ms 722272 KB Output is correct
45 Correct 394 ms 725048 KB Output is correct
46 Correct 385 ms 744916 KB Output is correct
47 Correct 481 ms 742160 KB Output is correct
48 Correct 442 ms 742152 KB Output is correct
49 Correct 526 ms 775360 KB Output is correct
50 Correct 525 ms 775320 KB Output is correct
51 Correct 453 ms 742524 KB Output is correct
52 Correct 429 ms 742220 KB Output is correct
53 Correct 465 ms 742292 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 704804 KB Output is correct
2 Correct 324 ms 704744 KB Output is correct
3 Correct 333 ms 704724 KB Output is correct
4 Correct 335 ms 704776 KB Output is correct
5 Correct 338 ms 704836 KB Output is correct
6 Correct 315 ms 704716 KB Output is correct
7 Correct 356 ms 704700 KB Output is correct
8 Incorrect 323 ms 704732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 704792 KB Output is correct
2 Correct 316 ms 704896 KB Output is correct
3 Correct 324 ms 704884 KB Output is correct
4 Correct 330 ms 704680 KB Output is correct
5 Correct 324 ms 704888 KB Output is correct
6 Correct 327 ms 704920 KB Output is correct
7 Correct 315 ms 704844 KB Output is correct
8 Correct 321 ms 704836 KB Output is correct
9 Correct 341 ms 704848 KB Output is correct
10 Correct 341 ms 704920 KB Output is correct
11 Correct 347 ms 704828 KB Output is correct
12 Correct 323 ms 704852 KB Output is correct
13 Correct 314 ms 704772 KB Output is correct
14 Incorrect 319 ms 704796 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 704804 KB Output is correct
2 Correct 324 ms 704744 KB Output is correct
3 Correct 333 ms 704724 KB Output is correct
4 Correct 335 ms 704776 KB Output is correct
5 Correct 338 ms 704836 KB Output is correct
6 Correct 315 ms 704716 KB Output is correct
7 Correct 356 ms 704700 KB Output is correct
8 Incorrect 323 ms 704732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 704804 KB Output is correct
2 Correct 324 ms 704744 KB Output is correct
3 Correct 333 ms 704724 KB Output is correct
4 Correct 335 ms 704776 KB Output is correct
5 Correct 338 ms 704836 KB Output is correct
6 Correct 315 ms 704716 KB Output is correct
7 Correct 356 ms 704700 KB Output is correct
8 Incorrect 323 ms 704732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 704808 KB Output is correct
2 Correct 331 ms 704768 KB Output is correct
3 Correct 356 ms 704844 KB Output is correct
4 Correct 329 ms 704824 KB Output is correct
5 Correct 331 ms 704784 KB Output is correct
6 Correct 353 ms 704832 KB Output is correct
7 Correct 335 ms 704856 KB Output is correct
8 Correct 393 ms 704856 KB Output is correct
9 Correct 384 ms 704696 KB Output is correct
10 Correct 381 ms 704688 KB Output is correct
11 Correct 352 ms 704696 KB Output is correct
12 Correct 368 ms 704808 KB Output is correct
13 Correct 380 ms 704808 KB Output is correct
14 Correct 355 ms 704912 KB Output is correct
15 Correct 335 ms 704808 KB Output is correct
16 Correct 349 ms 704796 KB Output is correct
17 Correct 335 ms 704876 KB Output is correct
18 Correct 449 ms 704716 KB Output is correct
19 Correct 389 ms 705960 KB Output is correct
20 Correct 366 ms 706948 KB Output is correct
21 Correct 340 ms 706344 KB Output is correct
22 Correct 359 ms 706008 KB Output is correct
23 Correct 333 ms 706000 KB Output is correct
24 Correct 329 ms 707560 KB Output is correct
25 Correct 334 ms 707756 KB Output is correct
26 Correct 322 ms 706016 KB Output is correct
27 Correct 317 ms 705996 KB Output is correct
28 Correct 314 ms 706012 KB Output is correct
29 Correct 353 ms 708096 KB Output is correct
30 Correct 320 ms 706800 KB Output is correct
31 Correct 381 ms 709240 KB Output is correct
32 Correct 350 ms 708172 KB Output is correct
33 Correct 343 ms 708084 KB Output is correct
34 Correct 348 ms 711760 KB Output is correct
35 Correct 356 ms 711860 KB Output is correct
36 Correct 333 ms 708248 KB Output is correct
37 Correct 330 ms 708220 KB Output is correct
38 Correct 331 ms 708168 KB Output is correct
39 Correct 454 ms 742148 KB Output is correct
40 Correct 355 ms 709012 KB Output is correct
41 Correct 341 ms 713416 KB Output is correct
42 Correct 346 ms 710008 KB Output is correct
43 Correct 348 ms 712512 KB Output is correct
44 Correct 364 ms 722272 KB Output is correct
45 Correct 394 ms 725048 KB Output is correct
46 Correct 385 ms 744916 KB Output is correct
47 Correct 481 ms 742160 KB Output is correct
48 Correct 442 ms 742152 KB Output is correct
49 Correct 526 ms 775360 KB Output is correct
50 Correct 525 ms 775320 KB Output is correct
51 Correct 453 ms 742524 KB Output is correct
52 Correct 429 ms 742220 KB Output is correct
53 Correct 465 ms 742292 KB Output is correct
54 Correct 326 ms 704804 KB Output is correct
55 Correct 324 ms 704744 KB Output is correct
56 Correct 333 ms 704724 KB Output is correct
57 Correct 335 ms 704776 KB Output is correct
58 Correct 338 ms 704836 KB Output is correct
59 Correct 315 ms 704716 KB Output is correct
60 Correct 356 ms 704700 KB Output is correct
61 Incorrect 323 ms 704732 KB Output isn't correct
62 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 704808 KB Output is correct
2 Correct 331 ms 704768 KB Output is correct
3 Correct 356 ms 704844 KB Output is correct
4 Correct 329 ms 704824 KB Output is correct
5 Correct 331 ms 704784 KB Output is correct
6 Correct 353 ms 704832 KB Output is correct
7 Correct 335 ms 704856 KB Output is correct
8 Correct 393 ms 704856 KB Output is correct
9 Correct 384 ms 704696 KB Output is correct
10 Correct 381 ms 704688 KB Output is correct
11 Correct 352 ms 704696 KB Output is correct
12 Correct 368 ms 704808 KB Output is correct
13 Correct 380 ms 704808 KB Output is correct
14 Correct 355 ms 704912 KB Output is correct
15 Correct 335 ms 704808 KB Output is correct
16 Correct 349 ms 704796 KB Output is correct
17 Correct 335 ms 704876 KB Output is correct
18 Correct 449 ms 704716 KB Output is correct
19 Correct 389 ms 705960 KB Output is correct
20 Correct 366 ms 706948 KB Output is correct
21 Correct 340 ms 706344 KB Output is correct
22 Correct 359 ms 706008 KB Output is correct
23 Correct 333 ms 706000 KB Output is correct
24 Correct 329 ms 707560 KB Output is correct
25 Correct 334 ms 707756 KB Output is correct
26 Correct 322 ms 706016 KB Output is correct
27 Correct 317 ms 705996 KB Output is correct
28 Correct 314 ms 706012 KB Output is correct
29 Correct 353 ms 708096 KB Output is correct
30 Correct 320 ms 706800 KB Output is correct
31 Correct 381 ms 709240 KB Output is correct
32 Correct 350 ms 708172 KB Output is correct
33 Correct 343 ms 708084 KB Output is correct
34 Correct 348 ms 711760 KB Output is correct
35 Correct 356 ms 711860 KB Output is correct
36 Correct 333 ms 708248 KB Output is correct
37 Correct 330 ms 708220 KB Output is correct
38 Correct 331 ms 708168 KB Output is correct
39 Correct 454 ms 742148 KB Output is correct
40 Correct 355 ms 709012 KB Output is correct
41 Correct 341 ms 713416 KB Output is correct
42 Correct 346 ms 710008 KB Output is correct
43 Correct 348 ms 712512 KB Output is correct
44 Correct 364 ms 722272 KB Output is correct
45 Correct 394 ms 725048 KB Output is correct
46 Correct 385 ms 744916 KB Output is correct
47 Correct 481 ms 742160 KB Output is correct
48 Correct 442 ms 742152 KB Output is correct
49 Correct 526 ms 775360 KB Output is correct
50 Correct 525 ms 775320 KB Output is correct
51 Correct 453 ms 742524 KB Output is correct
52 Correct 429 ms 742220 KB Output is correct
53 Correct 465 ms 742292 KB Output is correct
54 Correct 326 ms 704804 KB Output is correct
55 Correct 324 ms 704744 KB Output is correct
56 Correct 333 ms 704724 KB Output is correct
57 Correct 335 ms 704776 KB Output is correct
58 Correct 338 ms 704836 KB Output is correct
59 Correct 315 ms 704716 KB Output is correct
60 Correct 356 ms 704700 KB Output is correct
61 Incorrect 323 ms 704732 KB Output isn't correct
62 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 704808 KB Output is correct
2 Correct 331 ms 704768 KB Output is correct
3 Correct 356 ms 704844 KB Output is correct
4 Correct 329 ms 704824 KB Output is correct
5 Correct 331 ms 704784 KB Output is correct
6 Correct 353 ms 704832 KB Output is correct
7 Correct 335 ms 704856 KB Output is correct
8 Correct 393 ms 704856 KB Output is correct
9 Correct 384 ms 704696 KB Output is correct
10 Correct 381 ms 704688 KB Output is correct
11 Correct 352 ms 704696 KB Output is correct
12 Correct 368 ms 704808 KB Output is correct
13 Correct 380 ms 704808 KB Output is correct
14 Correct 355 ms 704912 KB Output is correct
15 Correct 335 ms 704808 KB Output is correct
16 Correct 349 ms 704796 KB Output is correct
17 Correct 335 ms 704876 KB Output is correct
18 Correct 449 ms 704716 KB Output is correct
19 Correct 389 ms 705960 KB Output is correct
20 Correct 366 ms 706948 KB Output is correct
21 Correct 340 ms 706344 KB Output is correct
22 Correct 359 ms 706008 KB Output is correct
23 Correct 333 ms 706000 KB Output is correct
24 Correct 329 ms 707560 KB Output is correct
25 Correct 334 ms 707756 KB Output is correct
26 Correct 322 ms 706016 KB Output is correct
27 Correct 317 ms 705996 KB Output is correct
28 Correct 314 ms 706012 KB Output is correct
29 Correct 353 ms 708096 KB Output is correct
30 Correct 320 ms 706800 KB Output is correct
31 Correct 381 ms 709240 KB Output is correct
32 Correct 350 ms 708172 KB Output is correct
33 Correct 343 ms 708084 KB Output is correct
34 Correct 348 ms 711760 KB Output is correct
35 Correct 356 ms 711860 KB Output is correct
36 Correct 333 ms 708248 KB Output is correct
37 Correct 330 ms 708220 KB Output is correct
38 Correct 331 ms 708168 KB Output is correct
39 Correct 454 ms 742148 KB Output is correct
40 Correct 355 ms 709012 KB Output is correct
41 Correct 341 ms 713416 KB Output is correct
42 Correct 346 ms 710008 KB Output is correct
43 Correct 348 ms 712512 KB Output is correct
44 Correct 364 ms 722272 KB Output is correct
45 Correct 394 ms 725048 KB Output is correct
46 Correct 385 ms 744916 KB Output is correct
47 Correct 481 ms 742160 KB Output is correct
48 Correct 442 ms 742152 KB Output is correct
49 Correct 526 ms 775360 KB Output is correct
50 Correct 525 ms 775320 KB Output is correct
51 Correct 453 ms 742524 KB Output is correct
52 Correct 429 ms 742220 KB Output is correct
53 Correct 465 ms 742292 KB Output is correct
54 Correct 326 ms 704804 KB Output is correct
55 Correct 324 ms 704744 KB Output is correct
56 Correct 333 ms 704724 KB Output is correct
57 Correct 335 ms 704776 KB Output is correct
58 Correct 338 ms 704836 KB Output is correct
59 Correct 315 ms 704716 KB Output is correct
60 Correct 356 ms 704700 KB Output is correct
61 Incorrect 323 ms 704732 KB Output isn't correct
62 Halted 0 ms 0 KB -