| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1132405 | henriess | The Kingdom of JOIOI (JOI17_joioi) | C++20 | 0 ms | 0 KiB |
#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;
}