Code : Gerrymandering

#include <atcoder/dsu>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const int inf = 1e5;

void solve(vector<int> &a, vector<pair<int, int>> &edges) {
    int n = a.size();

    int ans = inf;
    int full_mask = 1 << n;
    for (int mask = 1; mask < full_mask - 1; mask++) {
        dsu d(n);
        for (int i = 0; i < (int)edges.size(); i++) {
            int x = edges[i].first;
            int y = edges[i].second;
            bool xcolor = (1 << x) & mask;
            bool ycolor = (1 << y) & mask;
            if (xcolor != ycolor) {
                continue;
            }
            d.merge(x, y);
        }

        map<int, int> leader;

        int leader_cnt = 0;
        for (int i = 0; i < n; i++) {
            leader[d.leader(i)] += a[i];
        }
        if (leader.size() != 2) {
            continue;
        }

        int diff_now = abs(leader.begin()->second - leader.rbegin()->second);
        ans = min(ans, diff_now);
    }
    if (ans >= inf) {
        ans = -1;
    }
    cout << ans << endl;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<pair<int, int>> edges;
    for (int i = 0; i < n; i++) {
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int x;
            cin >> x;
            x--;
            edges.push_back({i, x});
        }
    }
    solve(a, edges);
    return 0;
}