Submission #1356403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356403		gay	Maze (JOI23_ho_t3)	C++20	Compilation error	0 ms	0 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

int R, C, N;
vector<string> grid;
vector<int> dist_arr;

// Одномерные DSU для быстрого пропуска уже пройденных ячеек
vector<int> p_col;
vector<int> p_row_inner;
vector<int> p_row_outer;

inline int find_col(int r, int c) {
    int idx = r * (C + 1) + c;
    if (p_col[idx] == c) return c;
    return p_col[idx] = find_col(r, p_col[idx]);
}

inline void remove_col(int r, int c) {
    int idx = r * (C + 1) + c;
    p_col[idx] = find_col(r, c + 1);
}

inline int find_row_inner(int r, int c) {
    int idx = r * C + c;
    if (p_row_inner[idx] == r) return r;
    return p_row_inner[idx] = find_row_inner(p_row_inner[idx], c);
}

inline int find_row_outer(int r, int c) {
    int idx = r * C + c;
    if (p_row_outer[idx] == r) return r;
    return p_row_outer[idx] = find_row_outer(p_row_outer[idx], c);
}

inline void remove_row_outer(int r, int c) {
    int idx = r * C + c;
    p_row_outer[idx] = find_row_outer(r + 1, c);
}

inline void remove_row_inner(int r, int c) {
    int idx = r * C + c;
    p_row_inner[idx] = find_row_inner(r + 1, c);
    remove_row_outer(r, c); // Inner-покрытие перекрывает outer, удаляем и оттуда
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> R >> C >> N)) return 0;

    int sr, sc, gr, gc;
    cin >> sr >> sc >> gr >> gc;
    sr--; sc--; gr--; gc--;

    grid.resize(R);
    for(int i = 0; i < R; ++i) {
        cin >> grid[i];
    }

    if (sr == gr && sc == gc) {
        cout << 0 << "\n";
        return 0;
    }

    dist_arr.assign(R * C, -1);
    p_col.resize(R * (C + 1));
    for(int r = 0; r < R; ++r) {
        for(int c = 0; c <= C; ++c) {
            p_col[r * (C + 1) + c] = c;
        }
    }

    p_row_inner.resize((R + 1) * C);
    p_row_outer.resize((R + 1) * C);
    for(int r = 0; r <= R; ++r) {
        for(int c = 0; c < C; ++c) {
            p_row_inner[r * C + c] = r;
            p_row_outer[r * C + c] = r;
        }
    }

    vector<pair<int, int>> Q_current;
    dist_arr[sr * C + sc] = 0;
    remove_col(sr, sc);
    Q_current.push_back({sr, sc});

    int level = 0;
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!Q_current.empty()) {
        queue<pair<int, int>> q0;
        for (auto p : Q_current) q0.push(p);
        C++
        
        


        vector<pair<int, int>> S_L;

        // 1. Сначала исследуем все клетки с нулевой стоимостью (по белым клеткам)
        while (!q0.empty()) {
            auto [r, c] = q0.front();
            q0.pop();
            S_L.push_back({r, c});

            if (r == gr && c == gc) {
                cout << level << "\n";
                return 0;
            }

            for (int i = 0; i < 4; ++i) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
                    if (grid[nr][nc] == '.') {
                        if (dist_arr[nr * C + nc] == -1) {
                            dist_arr[nr * C + nc] = level;
                            remove_col(nr, nc);
                            q0.push({nr, nc});
                        }
                    }
                }
            }
        }

        vector<pair<int, int>> Q1_inner, Q1_outer;

        // 2. Расширение по вертикали (имитация 1D прыжка для штампа)
        for (auto [r, c] : S_L) {
            // Внутренняя (широкая) вертикаль
            int min_r_in = max(0, r - N + 1);
            int max_r_in = min(R - 1, r + N - 1);
            int curr_r = find_row_inner(min_r_in, c);
            while (curr_r <= max_r_in) {
                Q1_inner.push_back({curr_r, c});
                remove_row_inner(curr_r, c);
                curr_r = find_row_inner(curr_r, c);
            }

            // Крайняя верхняя и нижняя граница действия штампа
            int r_out1 = r - N;
            if (r_out1 >= 0 && find_row_outer(r_out1, c) == r_out1) {
                Q1_outer.push_back({r_out1, c});
                remove_row_outer(r_out1, c);
            }

            int r_out2 = r + N;
            if (r_out2 < R && find_row_outer(r_out2, c) == r_out2) {
                Q1_outer.push_back({r_out2, c});
                remove_row_outer(r_out2, c);
            }
        }

        vector<pair<int, int>> Q_next;

        // 3. Расширение по горизонтали
        for (auto [r, c] : Q1_inner) {
            int min_c = max(0, c - N);
            int max_c = min(C - 1, c + N);
            int curr_c = find_col(r, min_c);
            while (curr_c <= max_c) {
                dist_arr[r * C + curr_c] = level + 1;
                remove_col(r, curr_c);
                Q_next.push_back({r, curr_c});
                curr_c = find_col(r, curr_c);
            }
        }

        for (auto [r, c] : Q1_outer) {
            int min_c = max(0, c - N + 1);
            int max_c = min(C - 1, c + N - 1);
            int curr_c = find_col(r, min_c);
            while (curr_c <= max_c) {
                dist_arr[r * C + curr_c] = level + 1;
                remove_col(r, curr_c);
                Q_next.push_back({r, curr_c});
                curr_c = find_col(r, curr_c);
            }
        }

        // Переходим на следующую "волну" штамповки
        Q_current = move(Q_next);
        level++;
    }

    return 0;
}

Compilation message (stderr)

Main.cpp:98:9: error: extended character  is not valid in an identifier
   98 |         
      |         ^
Main.cpp:99:9: error: extended character  is not valid in an identifier
   99 |         
      |         ^
Main.cpp: In function 'int main()':
Main.cpp:97:12: error: expected ';' before '\U0000e9e1'
   97 |         C++
      |            ^
      |            ;
   98 |         
      |         ~   
Main.cpp:108:13: error: 'S_L' was not declared in this scope
  108 |             S_L.push_back({r, c});
      |             ^~~
Main.cpp:133:28: error: 'S_L' was not declared in this scope
  133 |         for (auto [r, c] : S_L) {
      |                            ^~~
Main.cpp:139:35: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  139 |                 Q1_inner.push_back({curr_r, c});
      |                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from Main.cpp:2:
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::vector<std::pair<int, int> >::value_type&' {aka 'const std::pair<int, int>&'}
 1281 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1298 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
Main.cpp:147:35: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  147 |                 Q1_outer.push_back({r_out1, c});
      |                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::vector<std::pair<int, int> >::value_type&' {aka 'const std::pair<int, int>&'}
 1281 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1298 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
Main.cpp:153:35: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  153 |                 Q1_outer.push_back({r_out2, c});
      |                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::vector<std::pair<int, int> >::value_type&' {aka 'const std::pair<int, int>&'}
 1281 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1298 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~