Kubuś

#include <iostream>
#include <vector>
#include <bitset>

const int N = 21;
const int STANY = 2097152;
std::vector<int> tab[N];
int liczba_krawedzi[STANY];
int dp_max[STANY];
int n;
int dwadoentej = 1;
std::bitset<N> akt;
std::bitset<N> poprzedni;
char input[N];

int wynikStanu(int stan, int pop, int id_rozn) {
    akt = stan;
    poprzedni = pop;
    int kol_sasiedzi = 0;
    for (auto it : tab[n - id_rozn]) {
        if (poprzedni[n - it])
            kol_sasiedzi++;
    }
    return liczba_krawedzi[pop] + (int) tab[n - id_rozn].size() - 2 * kol_sasiedzi;
}

void obliczKraw() {
    int potega = 1;
    int id_rozn = 0;
    for (int i = 1; i <= n; i++)
        dwadoentej *= 2;
    for (int i = 1; i < dwadoentej; i++) {
        if (potega * 2 <= i) {
            potega *= 2;
            id_rozn++;
        }
        liczba_krawedzi[i] = wynikStanu(i, i ^ potega, id_rozn);
    }
}

void obliczDp() {
    for (int i = 1; i < dwadoentej; i++) {
        int max = liczba_krawedzi[i];
        akt = i;
        for (int j = 0; j < n; j++) {
            if (akt[j]) {
                akt[j] = false;
                max = std::max(max, dp_max[(int) akt.to_ulong()]);
                akt[j] = true;
            }
        }
        dp_max[i] = max;
    }
}

int binToDec() {
    int ret = 0;
    int pot = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (input[i] == '1')
            ret += pot;
        pot *= 2;
    }
    return ret;
}

int main() {
    int m, q, a, b;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        tab[a].push_back(b);
        tab[b].push_back(a);
    }
    obliczKraw();
    obliczDp();
    int x;
    while (q--) {
        scanf("%s", input);
        x = binToDec();
        printf("%d\n", dp_max[x]);
    }
    return 0;
}