Submission #1132405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132405		henriess	The Kingdom of JOIOI (JOI17_joioi)	C++20	Compilation error	0 ms	0 KiB

joioi

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

int H, W;
vector<vector<int>> altitude;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

// Check if a cell is within bounds
bool is_valid(int x, int y) {
    return x >= 0 && x < H && y >= 0 && y < W;
}

// Check if we can divide the grid into two regions with maximum altitude difference <= T
bool can_divide(int T) {
    vector<vector<bool>> visited(H, vector<bool>(W, false));
    vector<pair<int, int>> regions;

    auto bfs = [&](int sx, int sy) {
        queue<pair<int, int>> q;
        q.emplace(sx, sy);
        visited[sx][sy] = true;

        vector<pair<int, int>> cells;
        cells.emplace_back(sx, sy);

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (is_valid(nx, ny) && !visited[nx][ny] && abs(altitude[x][y] - altitude[nx][ny]) <= T) {
                    visited[nx][ny] = true;
                    q.emplace(nx, ny);
                    cells.emplace_back(nx, ny);
                }
            }
        }

        return cells;
    };

    // Find all connected components
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (!visited[i][j]) {
                regions.push_back(bfs(i, j));
            }
        }
    }

    // If we found exactly 2 connected regions, return true
    return regions.size() == 2;
}

int main() {
    cin >> H >> W;
    altitude.resize(H, vector<int>(W));

    int min_alt = INT_MAX, max_alt = INT_MIN;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> altitude[i][j];
            min_alt = min(min_alt, altitude[i][j]);
            max_alt = max(max_alt, altitude[i][j]);
        }
    }

    int left = 0, right = max_alt - min_alt;
    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (can_divide(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << result << endl;
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'bool can_divide(int)':
joioi.cpp:55:34: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(std::vector<std::pair<int, int> >)'
   55 |                 regions.push_back(bfs(i, j));
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from joioi.cpp:2:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~