제출 #1243718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243718		marcus06	Mecho (IOI09_mecho)	C++20	컴파일 에러	0 ms	0 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

/*How to use:
    Tvector <int, 2> g(n); //graph
    Tvector <int, 3> f(n, k, 2) = f[n][k][2]
*/
template <class Tp, int D = 1>
struct Tvector : public vector<Tvector<Tp, D - 1>> {
    template <class... Args>
    Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {}
};

template <class Tp>
struct Tvector<Tp, 1> : public vector<Tp> {
    Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {}
};

#ifdef LOCAL
#include </home/marcus06/CP/Library/debug.h>
#else
#define debug(...) 
#endif

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
 
void solve() {
    int n, s;
    cin >> n >> s;

    Tvector <char, 2> g(n, n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }

    int h_x, h_y;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == 'D') {
                h_x = i;
                h_y = j;
            }
        }
    }

    int m_x, m_y;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == 'M') {
                m_x = i;
                m_y = j;
            }
        }
    }

    auto valid = [&](int x, int y) -> bool {
        return (x >= 0 && y >= 0 && x < n && y < n && (g[x][y] == 'G' || g[x][y] == 'M'));
    };

    Tvector <int, 2> bee_dist(n, n);
    Tvector <bool, 2> bee_vis(n, n);
    {
        queue <pair <int, int>> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == 'H') {
                    bee_dist[i][j] = 0;
                    bee_vis[i][j] = true;
                    q.emplace(i, j);
                }
            }
        }
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int u = x + dx[i], v = y + dy[i];
                if (u == h_x && v == h_y) continue;
                if (valid(u, v) && !bee_vis[u][v]) {
                    bee_vis[u][v] = true;
                    bee_dist[u][v] = bee_dist[x][y] + 1;
                    q.emplace(u, v);
                }
            }
        }
    }

    Tvector <int, 2> Mecho_dist(n, n);
    Tvector <bool, 2> Mecho_vis(n, n);
    auto possible = [&](int t) -> bool {
        fill(Mecho_vis.begin(), Mecho_vis.end(), Tvector <int, 1>(n, false));

        queue <pair <int, int>> q;
        q.emplace(m_x, m_y);
        Mecho_dist[m_x][m_y] = 0;
        if (bee_dist[m_x][m_y] <= t) q.pop();

        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int u = x + dx[i], v = y + dy[i];
                if (valid(u, v) && !Mecho_vis[u][v]) {
                    int nxt_dist = t + Mecho_dist[x][y] / s;
                    if (nxt_dist < bee_dist[u][v]) {
                        Mecho_vis[u][v] = true;
                        Mecho_dist[u][v] = Mecho_dist[x][y] + 1;
                        q.emplace(u, v);
                    }
                }
            }
        }

        bool is_success = false;
        for (int i = 0; i < 4; ++i) {
            int u = h_x + dx[i], v = h_y + dy[i];
            if (valid(u, v) && Mecho_vis[u][v]) {
                if (t + Mecho_dist[u][v] / s < bee_dist[u][v]) is_success = true;
            }
        }
        return is_success;
    };

    int l = -1, r = int(1e9);
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (possible(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif

    int tt = 1;
    while (tt--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from mecho.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h: In instantiation of 'constexpr typename __gnu_cxx::__enable_if<(! std::__is_scalar<_Tp>::__value), void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = Tvector<bool, 1>*; _Tp = Tvector<int, 1>; typename __gnu_cxx::__enable_if<(! std::__is_scalar<_Tp>::__value), void>::__type = void]':
/usr/include/c++/11/bits/stl_algobase.h:953:21:   required from 'constexpr void std::__fill_a1(__gnu_cxx::__normal_iterator<_Iterator, _Container>, __gnu_cxx::__normal_iterator<_Iterator, _Container>, const _Tp&) [with _Ite = Tvector<bool, 1>*; _Cont = std::vector<Tvector<bool, 1>, std::allocator<Tvector<bool, 1> > >; _Tp = Tvector<int, 1>]'
/usr/include/c++/11/bits/stl_algobase.h:969:21:   required from 'constexpr void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = __gnu_cxx::__normal_iterator<Tvector<bool, 1>*, std::vector<Tvector<bool, 1>, std::allocator<Tvector<bool, 1> > > >; _Tp = Tvector<int, 1>]'
/usr/include/c++/11/bits/stl_algobase.h:999:20:   required from 'constexpr void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<Tvector<bool, 1>*, std::vector<Tvector<bool, 1>, std::allocator<Tvector<bool, 1> > > >; _Tp = Tvector<int, 1>]'
mecho.cpp:94:13:   required from here
/usr/include/c++/11/bits/stl_algobase.h:912:18: error: no match for 'operator=' (operand types are 'Tvector<bool, 1>' and 'const Tvector<int, 1>')
  912 |         *__first = __value;
      |         ~~~~~~~~~^~~~~~~~~
mecho.cpp:16:8: note: candidate: 'Tvector<bool, 1>& Tvector<bool, 1>::operator=(const Tvector<bool, 1>&)'
   16 | struct Tvector<Tp, 1> : public vector<Tp> {
      |        ^~~~~~~~~~~~~~
mecho.cpp:16:8: note:   no known conversion for argument 1 from 'const Tvector<int, 1>' to 'const Tvector<bool, 1>&'
mecho.cpp:16:8: note: candidate: 'Tvector<bool, 1>& Tvector<bool, 1>::operator=(Tvector<bool, 1>&&)'
mecho.cpp:16:8: note:   no known conversion for argument 1 from 'const Tvector<int, 1>' to 'Tvector<bool, 1>&&'