oj.uz

Submission #1090152

# Submission time Handle Problem Language Result Execution time Memory
1090152 2024-09-17T20:21:57 Z svorogaze Maze (JOI23_ho_t3) C++
35 / 100
 2000 ms 86188 KB 
/*
Disgrace. Humiliation. Unseemly and unwelcome at the feet of The Council.
Their eyes ablaze with bitter resentment, glaring through Gabriel’s wounds of body and soul,
bore outward for all to see.

"Has this one abandoned the way of our Creator?"
"It is unworthy of its Holy Light."
"The Father's Light is indomitable."
"This one only sees fit to squander it."

Their words resonated in Gabriel's limbs, coursing through as lightning upon wire,
a searing hiss that would strike lessers deaf and blind.
The Holy Light within him, an unstoppable storm of divine fury.
Insurmountable for mere objects.
This he knew.

"Holy Council, my devotion to our Creator is absolute.
I have never strayed from the will of the Father, but a machine-"

"You dare imply the might of the Father could be shaken by mere objects?"
"Impossible."
"Heresy."
"Unspeakable."
"Heresy."
"Heresy."
"Silence!"
"Your failure will not be tolerated. As punishment, the Father's Light shall be severed
from your body. You have 24 hours before the last of its embers die out."
"And you with them."
"Prove your loyalty."
"Unmake your mistakes."

As the Light was ripped from his being, Gabriel’s screams were silenced
in the hiss of gospel in praise of God.
A boiling anguish to which even the fires of hell could not compare.
Through the blaze of torment a single burning hatred was forged anew.

If the machines seek blood, he would give it freely; and with such fury, even metal will bleed.
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#define rep(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; ++j)
#define repk(n) for (int k = 0; k < n; ++k)
//#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, std::greater<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;
typedef tree<long long, null_type, greater_equal<>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define INF ((1ll << 30) - 1)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ld int
#define sq(x) ((x) * (x))
// 0 - even, 1 - odd (starting from 0)
#define MAXN 201000
char** carr;
bool** visited;
int** dist2;
int** dist3;
vector<pair<int, int>> v1;
int sr, sc, gr, gc;
int r, c, n;
int de = 0;
void dfs(int i, int j) {
    if (carr[i][j] != '.' && de > 0) return;
    if (!visited[i][j] || de == 0) {
        if (de != 0) {
            visited[i][j] = true;
            v1.push_back({i, j});
        }
        de++;
        if (i) {
            dfs(i - 1, j);
        }
        if (i + 1 < r) {
            dfs(i + 1, j);
        }
        if (j) {
            dfs(i, j - 1);
        }
        if (j + 1 < c) {
            dfs(i, j + 1);
        }
    }
}


auto main()->signed {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> r >> c >> n;
    cin >> sr >> sc >> gr >> gc;
    sr--, sc--;
    gr--, gc--;
    carr = new char*[r];
    for (int i = 0; i < r; ++i) {
        carr[i] = (new char[c]);
    }
    for (int i = 0; i < r; ++i) {
        string s;
        cin >> s;
        memcpy(carr[i], s.c_str(), sizeof(char) * c);
    }
    visited = new bool*[r];
    for (int i = 0; i < r; ++i) {
        visited[i] = new bool[c];
        memset(visited[i], 0, c);
    }
    dist2 = new int*[r];
    for (int i = 0; i < r; ++i) {
        dist2[i] = new int[c];
        for (int j = 0; j < c; ++j) {
            dist2[i][j] = INF;
        }
    }
    dist3 = new int*[r];
    for (int i = 0; i < r; ++i) {
        dist3[i] = new int[c];
        for (int j = 0; j < c; ++j) {
            dist3[i][j] = INF;
        }
    }
    visited[sr][sc] = true;
    v1.emplace_back(sr, sc);
    int cr = 0;
    while (true) {
        for (int i = 0; i < v1.size(); ++i) {
            if (v1[i].first == gr && v1[i].second == gc) {
                cout << cr;
                exit(0);
            }
            de = 0;
            dfs(v1[i].first, v1[i].second);
            dist2[v1[i].first][v1[i].second] = dist3[v1[i].first][v1[i].second] = 0;

        }
        for (int k = 0; k < v1.size(); ++k) {
            auto [i, j] = v1[k];
            if (dist2[i][j] == n) continue;
            if (j && !visited[i][j - 1]) {
                visited[i][j - 1] = true;
                v1.emplace_back(i, j - 1);
                dist2[i][j - 1] = dist2[i][j] + 1;
                dist3[i][j - 1] = 0;
            }
            if (j + 1 < c && !visited[i][j + 1]) {
                visited[i][j + 1] = true;
                v1.emplace_back(i, j + 1);
                dist2[i][j + 1] = dist2[i][j] + 1;
                dist3[i][j + 1] = 0;
            }
        }
        for (int k = 0; k < v1.size(); ++k) {
            auto [i, j] = v1[k];
            if (dist3[i][j] == n) continue;
            if (i && !visited[i - 1][j]) {
                visited[i - 1][j] = true;
                v1.emplace_back(i - 1, j);
                dist3[i - 1][j] = dist3[i][j] + 1;
                dist2[i - 1][j] = dist2[i][j];
            }
            if (i + 1 < r && !visited[i + 1][j]) {
                visited[i + 1][j] = true;
                v1.push_back({i + 1, j});
                dist3[i + 1][j] = dist3[i][j] + 1;
                dist2[i + 1][j] = dist2[i][j];
            }
        }
        vector<pair<int, int>> nw;
        nw.reserve(v1.size());
        for (auto i : v1) {
            if (dist2[i.first][i.second] + dist3[i.first][i.second] < 2 * n) {
                nw.push_back(i);
            } else {
                visited[i.first][i.second] = false;
            }
        }
        v1 = std::move(nw);
        cr++;
    }

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:134:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for (int i = 0; i < v1.size(); ++i) {
      |                         ~~^~~~~~~~~~~
Main.cpp:144:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for (int k = 0; k < v1.size(); ++k) {
      |                         ~~^~~~~~~~~~~
Main.cpp:145:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  145 |             auto [i, j] = v1[k];
      |                  ^
Main.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for (int k = 0; k < v1.size(); ++k) {
      |                         ~~^~~~~~~~~~~
Main.cpp:161:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  161 |             auto [i, j] = v1[k];
      |                  ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 83 ms 2296 KB Output is correct
20 Execution timed out 2060 ms 1612 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 3 ms 2272 KB Output is correct
27 Correct 3 ms 3028 KB Output is correct
28 Correct 4 ms 2776 KB Output is correct
29 Correct 3 ms 2004 KB Output is correct
30 Correct 2 ms 2004 KB Output is correct
31 Correct 6 ms 1376 KB Output is correct
32 Correct 1 ms 1112 KB Output is correct
33 Correct 2 ms 1112 KB Output is correct
34 Correct 8 ms 4824 KB Output is correct
35 Correct 7 ms 6608 KB Output is correct
36 Correct 11 ms 9680 KB Output is correct
37 Correct 8 ms 4228 KB Output is correct
38 Correct 4 ms 4300 KB Output is correct
39 Correct 26 ms 15396 KB Output is correct
40 Correct 66 ms 29712 KB Output is correct
41 Correct 113 ms 85456 KB Output is correct
42 Correct 117 ms 86188 KB Output is correct
43 Correct 67 ms 38848 KB Output is correct
44 Correct 48 ms 38856 KB Output is correct
45 Correct 70 ms 31900 KB Output is correct
46 Correct 61 ms 32952 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 85 ms 2232 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 7 ms 588 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Execution timed out 2094 ms 1692 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 85 ms 2232 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 7 ms 588 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Execution timed out 2094 ms 1692 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 83 ms 2296 KB Output is correct
20 Execution timed out 2060 ms 1612 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 83 ms 2296 KB Output is correct
20 Execution timed out 2060 ms 1612 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 83 ms 2296 KB Output is correct
20 Execution timed out 2060 ms 1612 KB Time limit exceeded
21 Halted 0 ms 0 KB -