Problem Overview The prisoners problem involves assigning prisoners to two cells such that prisoners with high hostility are separated. Each prisoner has a hostility level with other prisoners, and we need to find the maximum hsotility level that can be guaranteed to separate.

Solution 1: Union-Find with Type Tracking This approach uses a union-find data structure with type tracking to manage relationships between prisoners.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct UnionFind {
    vector<int> parent;
    vector<int> rank;
    int size;

    UnionFind(int n) : size(n), parent(n * 2), rank(n * 2, 0) {
        for (int i = 0; i < n * 2; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

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

    int n, m;
    cin >> n >> m;
    
    vector<pair<int, pair<int, int>>> conflicts;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        conflicts.emplace_back(w, make_pair(u, v));
    }

    sort(conflicts.begin(), conflicts.end(), greater<pair<int, pair<int, int>>>());

    UnionFind uf(n);
    int result = 0;
    
    for (const auto& conflict : conflicts) {
        int hostility = conflict.first;
        int prisoner1 = conflict.second.first;
        int prisoner2 = conflict.second.second;
        
        if (uf.find(prisoner1) == uf.find(prisoner2) || 
            uf.find(prisoner1 + n) == uf.find(prisoner2 + n)) {
            result = hostility;
            break;
        }
        
        uf.unite(prisoner1 + n, prisoner2);
        uf.unite(prisoner2 + n, prisoner1);
    }

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

Solution 2: Binary Search with Bipartite Graph This approach uses binary search combined with bipartite graph coloring to determine the maximum hostility level.

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

using namespace std;

bool isBipartite(const vector<vector<pair<int, int>>>& graph, int threshold) {
    vector<int> colors(graph.size(), -1);
    
    for (int i = 1; i < graph.size(); ++i) {
        if (colors[i] == -1) {
            queue<int> q;
            q.push(i);
            colors[i] = 0;
            
            while (!q.empty()) {
                int current = q.front();
                q.pop();
                
                for (const auto& neighbor : graph[current]) {
                    int next = neighbor.first;
                    int weight = neighbor.second;
                    
                    if (weight > threshold) {
                        if (colors[next] == -1) {
                            colors[next] = 1 - colors[current];
                            q.push(next);
                        } else if (colors[next] == colors[current]) {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}

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

    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    int left = 0, right = 1e9, answer = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (isBipartite(graph, mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer << endl;
    return 0;
}