Submission #1090151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090151		svorogaze	Maze (JOI23_ho_t3)	C++17	35 / 100	2099 ms	86172 KiB

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 (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 (stderr)

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: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) {
      |                         ~~^~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6