ACM Solution to the 2012 Europe 'kingdom bankruptcy' problem

acm-bankruptcy.cpp

#include <iostream>
#include <vector>
#include <bitset>
#include <set>
using namespace std;

#define LOG_LEVEL 0
#define DEBUG(s) { \
    if (LOG_LEVEL) { std::cerr << s << endl; } \
}

const int MAX_K = 20;
vector<vector<int> > debtMatrix;
bitset<MAX_K> reachable;
bitset<MAX_K> bankrupt;
set<unsigned long> visited;

bool isBankrupt (int kingdom, int n) {
    int score = 0;
    for (int i = 0; i < n; i++) {
        if (! bankrupt[i]) {
            score += debtMatrix[i][kingdom];
        }
    }
    return score < 0;
}

/**
 * Count is the number of bits flipped
 */
void DFS(int count, int n) {
    visited.insert(bankrupt.to_ulong());

    if (count == n - 1) {
        // find the last kingdom standing
        for (int i = 0; i < n; i++) {
            if (! bankrupt[i]) {
                reachable[i] = 1;
                break;
            }
        }

        return;
    }

    for (int i = 0; i < n; i++) {
        if (! bankrupt[i] && isBankrupt(i, n)) {
            bankrupt[i] = 1;
            // make sure that we haven't explored this route before
            if (visited.find(bankrupt.to_ulong()) == visited.end()) {
                DFS(count + 1, n);
            }
            // undo the op
            bankrupt[i] = 0;
        }
    }
}

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    cerr.sync_with_stdio(false);

    int T;
    cin >> T;
    int n, tmp;

    for  (int t = 0; t < T; t++) {
        cin >> n;

        debtMatrix.clear();
        reachable.reset();
        visited.clear();
        bankrupt.reset();

        for (int i = 0; i < n; i++) {
            vector<int> debtRow (n);

            for (int k = 0; k < n; k++) {
                cin >> debtRow[k];
            }

            debtMatrix.push_back(debtRow);
        }

        DFS(0, n);
        DEBUG(visited.size());
        int j = 0;
        //DEBUG("j");
        for (int i = 0; i < n; i++) {
            if (reachable[i]) {
                if (j > 0) cout << " ";
                cout << (i + 1);
                j++;
            }
        }

        if (j == 0) {
            cout << 0;
        }

        cout << endl;
    }

    return 0;
}