Submission #1132407

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

// Flood-fill to check connectivity
void flood_fill(int x, int y, int min_alt, int max_alt, vector<vector<bool>> &visited) {
    queue<pair<int, int>> q;
    q.emplace(x, y);
    visited[x][y] = true;

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

        for (int d = 0; d < 4; ++d) {
            int nx = cx + dx[d];
            int ny = cy + dy[d];

            if (is_valid(nx, ny) && !visited[nx][ny] && 
                altitude[nx][ny] >= min_alt && altitude[nx][ny] <= max_alt) {
                visited[nx][ny] = true;
                q.emplace(nx, ny);
            }
        }
    }
}

// Check if it's possible to divide the grid into 2 regions with max altitude difference <= T
bool can_divide(int T) {
    int min_alt = INT_MAX, max_alt = INT_MIN;

    // Determine global min/max altitude
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            min_alt = min(min_alt, altitude[i][j]);
            max_alt = max(max_alt, altitude[i][j]);
        }
    }

    for (int lower_bound = min_alt; lower_bound <= max_alt; ++lower_bound) {
        int upper_bound = lower_bound + T;
        if (upper_bound > max_alt) break;

        vector<vector<bool>> visited(H, vector<bool>(W, false));
        int regions_count = 0;

        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                if (!visited[i][j] && altitude[i][j] >= lower_bound && altitude[i][j] <= upper_bound) {
                    ++regions_count;
                    if (regions_count > 2) return false; // Early exit if more than 2 regions
                    flood_fill(i, j, lower_bound, upper_bound, visited);
                }
            }
        }

        if (regions_count == 2) return true; // Valid division found
    }

    return false; // No valid division found for this T
}

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

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> altitude[i][j];
        }
    }

    int left = 0, right = INT_MAX, result = INT_MAX;

    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;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40