답안 #1090154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090154	2024-09-17T20:27:06 Z	svorogaze	Maze (JOI23_ho_t3)	C++17	16 / 100	101 ms	86184 KB

Main

/*
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 (!visited[i][j]) {
            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;
    int sum = 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;

        }
        sum += v1.size();
        if (sum > 4 * r * c || v1.empty()) exit(100);
        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 && dist2[i.first][i.second] + dist3[i.first][i.second] > 0) {
                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:135: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]
  135 |         for (int i = 0; i < v1.size(); ++i) {
      |                         ~~^~~~~~~~~~~
Main.cpp:147: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]
  147 |         for (int k = 0; k < v1.size(); ++k) {
      |                         ~~^~~~~~~~~~~
Main.cpp:163: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]
  163 |         for (int k = 0; k < v1.size(); ++k) {
      |                         ~~^~~~~~~~~~~

Subtask #1
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Runtime error	0 ms	348 KB	Execution failed because the return code was nonzero
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 19.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Runtime error	348 KB	Execution failed because the return code was nonzero
6	Halted	0 KB	-

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	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	0 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	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 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	388 KB	Output is correct
20	Correct	0 ms	344 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 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	2 ms	2272 KB	Output is correct
27	Correct	3 ms	3028 KB	Output is correct
28	Correct	4 ms	2728 KB	Output is correct
29	Correct	4 ms	2004 KB	Output is correct
30	Correct	2 ms	2000 KB	Output is correct
31	Correct	4 ms	1388 KB	Output is correct
32	Correct	1 ms	1116 KB	Output is correct
33	Correct	1 ms	1116 KB	Output is correct
34	Correct	7 ms	4828 KB	Output is correct
35	Correct	7 ms	6608 KB	Output is correct
36	Correct	10 ms	9680 KB	Output is correct
37	Correct	8 ms	4412 KB	Output is correct
38	Correct	4 ms	4296 KB	Output is correct
39	Correct	19 ms	15320 KB	Output is correct
40	Correct	59 ms	29892 KB	Output is correct
41	Correct	94 ms	85400 KB	Output is correct
42	Correct	101 ms	86184 KB	Output is correct
43	Correct	66 ms	38848 KB	Output is correct
44	Correct	47 ms	38744 KB	Output is correct
45	Correct	66 ms	31864 KB	Output is correct
46	Correct	60 ms	32944 KB	Output is correct

Subtask #4
0 / 19.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Runtime error	348 KB	Execution failed because the return code was nonzero
6	Halted	0 KB	-

Subtask #5
0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Runtime error	348 KB	Execution failed because the return code was nonzero
6	Halted	0 KB	-

Subtask #6
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Runtime error	0 ms	348 KB	Execution failed because the return code was nonzero
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Runtime error	0 ms	348 KB	Execution failed because the return code was nonzero
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Runtime error	0 ms	348 KB	Execution failed because the return code was nonzero
4	Halted	0 ms	0 KB	-