oj.uz

Submission #739014

# Submission time Handle Problem Language Result Execution time Memory
739014 2023-05-09T18:37:19 Z He_Huanglu Maze (JOI23_ho_t3) C++17
24 / 100
 641 ms 776076 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

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

void up(int u, int v, int val) {
    if(0 < u && u <= m && 0 < v && v <= n && !f[u][v]) {
        q[1].push({u, v});
        f[u][v] = val;
    }
}

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]) {
            q[1].push({id, u});
            f[id][u] = val;
        }
        if(!t && !f[u][id]) {
            q[1].push({u, id});
            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(0 < u && u <= m && 0 < 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(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]) {
                        if(i == x - s && (j == y - s || j == y + s)) continue ;
                        if(i == x + s && (j == y - s || j == y + s)) continue ;
                        f[i][j] = f[x][y] + 1;
                        q[1].push({i, j});
                    }
                } ok[x][y] = 1;
                continue ;
            }
            int val = f[x][y] + 1;
            for(int i = 0; i < 4; i++) {
                int u = x + dx[i], v = y + dy[i];
                if(0 < u && u <= m && 0 < v && v <= n && ok[u][v]) {
                    if(i == 0) {
                        up(x - s, y + s - 1, val);
                        up(x + s, y + s - 1, val);
                        if(y + s <= n) upd(0, y + s, max(1, x - s + 1), min(m, x + s - 1), val);
                    }
                    if(i == 1) {
                        up(x + s - 1, y - s, val);
                        up(x + s - 1, y + s, val);
                        if(x + s <= m) upd(1, x + s, max(1, y - s + 1), min(n, y + s - 1), val);
                    }
                    if(i == 2) {
                        up(x - s, y - s + 1, val);
                        up(x + s, y - s + 1, val);
                        if(y > s) upd(0, y - s, max(1, x - s + 1), min(m, x + s - 1), val);
                    }
                    if(i == 3) {
                        up(x - s + 1, y - s, val);
                        up(x - s + 1, y + s, val);
                        if(x > s) upd(1, x - s, max(1, y - s + 1), min(n, y + s - 1), val);
                    }
                }
            } ok[x][y] = 1;
        }
    }
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 704760 KB Output is correct
2 Correct 348 ms 704708 KB Output is correct
3 Correct 405 ms 704832 KB Output is correct
4 Correct 378 ms 704844 KB Output is correct
5 Correct 367 ms 704792 KB Output is correct
6 Correct 378 ms 704844 KB Output is correct
7 Correct 370 ms 704740 KB Output is correct
8 Correct 394 ms 704748 KB Output is correct
9 Correct 395 ms 704776 KB Output is correct
10 Correct 352 ms 704784 KB Output is correct
11 Correct 397 ms 704772 KB Output is correct
12 Correct 362 ms 704700 KB Output is correct
13 Correct 399 ms 704820 KB Output is correct
14 Correct 354 ms 704692 KB Output is correct
15 Correct 351 ms 704808 KB Output is correct
16 Correct 333 ms 704900 KB Output is correct
17 Correct 340 ms 704844 KB Output is correct
18 Correct 326 ms 704980 KB Output is correct
19 Correct 331 ms 706076 KB Output is correct
20 Correct 340 ms 706968 KB Output is correct
21 Correct 334 ms 706352 KB Output is correct
22 Correct 370 ms 706092 KB Output is correct
23 Correct 331 ms 706076 KB Output is correct
24 Correct 337 ms 707688 KB Output is correct
25 Correct 338 ms 707700 KB Output is correct
26 Correct 339 ms 706132 KB Output is correct
27 Correct 328 ms 705996 KB Output is correct
28 Correct 329 ms 706012 KB Output is correct
29 Correct 352 ms 708228 KB Output is correct
30 Correct 368 ms 706696 KB Output is correct
31 Correct 347 ms 709392 KB Output is correct
32 Correct 361 ms 708300 KB Output is correct
33 Correct 365 ms 708308 KB Output is correct
34 Correct 354 ms 711844 KB Output is correct
35 Correct 361 ms 711972 KB Output is correct
36 Correct 337 ms 708328 KB Output is correct
37 Correct 347 ms 708180 KB Output is correct
38 Correct 330 ms 708184 KB Output is correct
39 Correct 620 ms 742316 KB Output is correct
40 Correct 335 ms 709068 KB Output is correct
41 Correct 353 ms 713680 KB Output is correct
42 Correct 364 ms 709944 KB Output is correct
43 Correct 361 ms 712500 KB Output is correct
44 Correct 388 ms 722308 KB Output is correct
45 Correct 395 ms 725024 KB Output is correct
46 Correct 382 ms 745424 KB Output is correct
47 Correct 641 ms 742816 KB Output is correct
48 Correct 568 ms 742632 KB Output is correct
49 Correct 552 ms 776076 KB Output is correct
50 Correct 641 ms 775952 KB Output is correct
51 Correct 590 ms 743312 KB Output is correct
52 Correct 496 ms 742984 KB Output is correct
53 Correct 571 ms 743048 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 704752 KB Output is correct
2 Correct 328 ms 704844 KB Output is correct
3 Correct 326 ms 704784 KB Output is correct
4 Correct 322 ms 704692 KB Output is correct
5 Correct 323 ms 704860 KB Output is correct
6 Correct 328 ms 704828 KB Output is correct
7 Correct 326 ms 704684 KB Output is correct
8 Incorrect 325 ms 704760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 704732 KB Output is correct
2 Correct 347 ms 704888 KB Output is correct
3 Correct 371 ms 704716 KB Output is correct
4 Correct 323 ms 704884 KB Output is correct
5 Correct 325 ms 704728 KB Output is correct
6 Correct 324 ms 704820 KB Output is correct
7 Correct 329 ms 704816 KB Output is correct
8 Correct 328 ms 704812 KB Output is correct
9 Correct 338 ms 704724 KB Output is correct
10 Correct 324 ms 704844 KB Output is correct
11 Correct 328 ms 704876 KB Output is correct
12 Correct 320 ms 704864 KB Output is correct
13 Correct 337 ms 704688 KB Output is correct
14 Correct 321 ms 704840 KB Output is correct
15 Correct 350 ms 704924 KB Output is correct
16 Correct 327 ms 704772 KB Output is correct
17 Correct 326 ms 704940 KB Output is correct
18 Correct 326 ms 704700 KB Output is correct
19 Correct 326 ms 704916 KB Output is correct
20 Correct 323 ms 704792 KB Output is correct
21 Correct 325 ms 704772 KB Output is correct
22 Correct 331 ms 704960 KB Output is correct
23 Correct 326 ms 704844 KB Output is correct
24 Correct 355 ms 704832 KB Output is correct
25 Correct 333 ms 705784 KB Output is correct
26 Correct 343 ms 706436 KB Output is correct
27 Correct 328 ms 706380 KB Output is correct
28 Correct 327 ms 706472 KB Output is correct
29 Correct 330 ms 706532 KB Output is correct
30 Correct 331 ms 706512 KB Output is correct
31 Correct 334 ms 706100 KB Output is correct
32 Correct 323 ms 706040 KB Output is correct
33 Correct 333 ms 706192 KB Output is correct
34 Correct 331 ms 708308 KB Output is correct
35 Correct 333 ms 709428 KB Output is correct
36 Correct 332 ms 709248 KB Output is correct
37 Correct 332 ms 709560 KB Output is correct
38 Correct 336 ms 709560 KB Output is correct
39 Correct 358 ms 717436 KB Output is correct
40 Correct 415 ms 738844 KB Output is correct
41 Correct 390 ms 745672 KB Output is correct
42 Correct 438 ms 753236 KB Output is correct
43 Correct 409 ms 755404 KB Output is correct
44 Correct 409 ms 755448 KB Output is correct
45 Correct 421 ms 746148 KB Output is correct
46 Correct 402 ms 741964 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 704752 KB Output is correct
2 Correct 328 ms 704844 KB Output is correct
3 Correct 326 ms 704784 KB Output is correct
4 Correct 322 ms 704692 KB Output is correct
5 Correct 323 ms 704860 KB Output is correct
6 Correct 328 ms 704828 KB Output is correct
7 Correct 326 ms 704684 KB Output is correct
8 Incorrect 325 ms 704760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 704752 KB Output is correct
2 Correct 328 ms 704844 KB Output is correct
3 Correct 326 ms 704784 KB Output is correct
4 Correct 322 ms 704692 KB Output is correct
5 Correct 323 ms 704860 KB Output is correct
6 Correct 328 ms 704828 KB Output is correct
7 Correct 326 ms 704684 KB Output is correct
8 Incorrect 325 ms 704760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 704760 KB Output is correct
2 Correct 348 ms 704708 KB Output is correct
3 Correct 405 ms 704832 KB Output is correct
4 Correct 378 ms 704844 KB Output is correct
5 Correct 367 ms 704792 KB Output is correct
6 Correct 378 ms 704844 KB Output is correct
7 Correct 370 ms 704740 KB Output is correct
8 Correct 394 ms 704748 KB Output is correct
9 Correct 395 ms 704776 KB Output is correct
10 Correct 352 ms 704784 KB Output is correct
11 Correct 397 ms 704772 KB Output is correct
12 Correct 362 ms 704700 KB Output is correct
13 Correct 399 ms 704820 KB Output is correct
14 Correct 354 ms 704692 KB Output is correct
15 Correct 351 ms 704808 KB Output is correct
16 Correct 333 ms 704900 KB Output is correct
17 Correct 340 ms 704844 KB Output is correct
18 Correct 326 ms 704980 KB Output is correct
19 Correct 331 ms 706076 KB Output is correct
20 Correct 340 ms 706968 KB Output is correct
21 Correct 334 ms 706352 KB Output is correct
22 Correct 370 ms 706092 KB Output is correct
23 Correct 331 ms 706076 KB Output is correct
24 Correct 337 ms 707688 KB Output is correct
25 Correct 338 ms 707700 KB Output is correct
26 Correct 339 ms 706132 KB Output is correct
27 Correct 328 ms 705996 KB Output is correct
28 Correct 329 ms 706012 KB Output is correct
29 Correct 352 ms 708228 KB Output is correct
30 Correct 368 ms 706696 KB Output is correct
31 Correct 347 ms 709392 KB Output is correct
32 Correct 361 ms 708300 KB Output is correct
33 Correct 365 ms 708308 KB Output is correct
34 Correct 354 ms 711844 KB Output is correct
35 Correct 361 ms 711972 KB Output is correct
36 Correct 337 ms 708328 KB Output is correct
37 Correct 347 ms 708180 KB Output is correct
38 Correct 330 ms 708184 KB Output is correct
39 Correct 620 ms 742316 KB Output is correct
40 Correct 335 ms 709068 KB Output is correct
41 Correct 353 ms 713680 KB Output is correct
42 Correct 364 ms 709944 KB Output is correct
43 Correct 361 ms 712500 KB Output is correct
44 Correct 388 ms 722308 KB Output is correct
45 Correct 395 ms 725024 KB Output is correct
46 Correct 382 ms 745424 KB Output is correct
47 Correct 641 ms 742816 KB Output is correct
48 Correct 568 ms 742632 KB Output is correct
49 Correct 552 ms 776076 KB Output is correct
50 Correct 641 ms 775952 KB Output is correct
51 Correct 590 ms 743312 KB Output is correct
52 Correct 496 ms 742984 KB Output is correct
53 Correct 571 ms 743048 KB Output is correct
54 Correct 341 ms 704752 KB Output is correct
55 Correct 328 ms 704844 KB Output is correct
56 Correct 326 ms 704784 KB Output is correct
57 Correct 322 ms 704692 KB Output is correct
58 Correct 323 ms 704860 KB Output is correct
59 Correct 328 ms 704828 KB Output is correct
60 Correct 326 ms 704684 KB Output is correct
61 Incorrect 325 ms 704760 KB Output isn't correct
62 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 704760 KB Output is correct
2 Correct 348 ms 704708 KB Output is correct
3 Correct 405 ms 704832 KB Output is correct
4 Correct 378 ms 704844 KB Output is correct
5 Correct 367 ms 704792 KB Output is correct
6 Correct 378 ms 704844 KB Output is correct
7 Correct 370 ms 704740 KB Output is correct
8 Correct 394 ms 704748 KB Output is correct
9 Correct 395 ms 704776 KB Output is correct
10 Correct 352 ms 704784 KB Output is correct
11 Correct 397 ms 704772 KB Output is correct
12 Correct 362 ms 704700 KB Output is correct
13 Correct 399 ms 704820 KB Output is correct
14 Correct 354 ms 704692 KB Output is correct
15 Correct 351 ms 704808 KB Output is correct
16 Correct 333 ms 704900 KB Output is correct
17 Correct 340 ms 704844 KB Output is correct
18 Correct 326 ms 704980 KB Output is correct
19 Correct 331 ms 706076 KB Output is correct
20 Correct 340 ms 706968 KB Output is correct
21 Correct 334 ms 706352 KB Output is correct
22 Correct 370 ms 706092 KB Output is correct
23 Correct 331 ms 706076 KB Output is correct
24 Correct 337 ms 707688 KB Output is correct
25 Correct 338 ms 707700 KB Output is correct
26 Correct 339 ms 706132 KB Output is correct
27 Correct 328 ms 705996 KB Output is correct
28 Correct 329 ms 706012 KB Output is correct
29 Correct 352 ms 708228 KB Output is correct
30 Correct 368 ms 706696 KB Output is correct
31 Correct 347 ms 709392 KB Output is correct
32 Correct 361 ms 708300 KB Output is correct
33 Correct 365 ms 708308 KB Output is correct
34 Correct 354 ms 711844 KB Output is correct
35 Correct 361 ms 711972 KB Output is correct
36 Correct 337 ms 708328 KB Output is correct
37 Correct 347 ms 708180 KB Output is correct
38 Correct 330 ms 708184 KB Output is correct
39 Correct 620 ms 742316 KB Output is correct
40 Correct 335 ms 709068 KB Output is correct
41 Correct 353 ms 713680 KB Output is correct
42 Correct 364 ms 709944 KB Output is correct
43 Correct 361 ms 712500 KB Output is correct
44 Correct 388 ms 722308 KB Output is correct
45 Correct 395 ms 725024 KB Output is correct
46 Correct 382 ms 745424 KB Output is correct
47 Correct 641 ms 742816 KB Output is correct
48 Correct 568 ms 742632 KB Output is correct
49 Correct 552 ms 776076 KB Output is correct
50 Correct 641 ms 775952 KB Output is correct
51 Correct 590 ms 743312 KB Output is correct
52 Correct 496 ms 742984 KB Output is correct
53 Correct 571 ms 743048 KB Output is correct
54 Correct 341 ms 704752 KB Output is correct
55 Correct 328 ms 704844 KB Output is correct
56 Correct 326 ms 704784 KB Output is correct
57 Correct 322 ms 704692 KB Output is correct
58 Correct 323 ms 704860 KB Output is correct
59 Correct 328 ms 704828 KB Output is correct
60 Correct 326 ms 704684 KB Output is correct
61 Incorrect 325 ms 704760 KB Output isn't correct
62 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 704760 KB Output is correct
2 Correct 348 ms 704708 KB Output is correct
3 Correct 405 ms 704832 KB Output is correct
4 Correct 378 ms 704844 KB Output is correct
5 Correct 367 ms 704792 KB Output is correct
6 Correct 378 ms 704844 KB Output is correct
7 Correct 370 ms 704740 KB Output is correct
8 Correct 394 ms 704748 KB Output is correct
9 Correct 395 ms 704776 KB Output is correct
10 Correct 352 ms 704784 KB Output is correct
11 Correct 397 ms 704772 KB Output is correct
12 Correct 362 ms 704700 KB Output is correct
13 Correct 399 ms 704820 KB Output is correct
14 Correct 354 ms 704692 KB Output is correct
15 Correct 351 ms 704808 KB Output is correct
16 Correct 333 ms 704900 KB Output is correct
17 Correct 340 ms 704844 KB Output is correct
18 Correct 326 ms 704980 KB Output is correct
19 Correct 331 ms 706076 KB Output is correct
20 Correct 340 ms 706968 KB Output is correct
21 Correct 334 ms 706352 KB Output is correct
22 Correct 370 ms 706092 KB Output is correct
23 Correct 331 ms 706076 KB Output is correct
24 Correct 337 ms 707688 KB Output is correct
25 Correct 338 ms 707700 KB Output is correct
26 Correct 339 ms 706132 KB Output is correct
27 Correct 328 ms 705996 KB Output is correct
28 Correct 329 ms 706012 KB Output is correct
29 Correct 352 ms 708228 KB Output is correct
30 Correct 368 ms 706696 KB Output is correct
31 Correct 347 ms 709392 KB Output is correct
32 Correct 361 ms 708300 KB Output is correct
33 Correct 365 ms 708308 KB Output is correct
34 Correct 354 ms 711844 KB Output is correct
35 Correct 361 ms 711972 KB Output is correct
36 Correct 337 ms 708328 KB Output is correct
37 Correct 347 ms 708180 KB Output is correct
38 Correct 330 ms 708184 KB Output is correct
39 Correct 620 ms 742316 KB Output is correct
40 Correct 335 ms 709068 KB Output is correct
41 Correct 353 ms 713680 KB Output is correct
42 Correct 364 ms 709944 KB Output is correct
43 Correct 361 ms 712500 KB Output is correct
44 Correct 388 ms 722308 KB Output is correct
45 Correct 395 ms 725024 KB Output is correct
46 Correct 382 ms 745424 KB Output is correct
47 Correct 641 ms 742816 KB Output is correct
48 Correct 568 ms 742632 KB Output is correct
49 Correct 552 ms 776076 KB Output is correct
50 Correct 641 ms 775952 KB Output is correct
51 Correct 590 ms 743312 KB Output is correct
52 Correct 496 ms 742984 KB Output is correct
53 Correct 571 ms 743048 KB Output is correct
54 Correct 341 ms 704752 KB Output is correct
55 Correct 328 ms 704844 KB Output is correct
56 Correct 326 ms 704784 KB Output is correct
57 Correct 322 ms 704692 KB Output is correct
58 Correct 323 ms 704860 KB Output is correct
59 Correct 328 ms 704828 KB Output is correct
60 Correct 326 ms 704684 KB Output is correct
61 Incorrect 325 ms 704760 KB Output isn't correct
62 Halted 0 ms 0 KB -