agents

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


vector<vector<int>> graph;
vector<int> taken;
vector<int> mapping;

int As;
int Bs;
int aPlaced = 0;
int bPlaced = 0;
int singleA = 0;
int singleB = 0;
bool second = false;
int bestScore;
int graphSize;

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

vector<int> getSortedGraph()
{
    vector<int> sizes(graphSize, 0);
    vector<int> newGraph(graphSize);
    for (int i = 0; i < graphSize; i++)
    {
        newGraph[i] = i;
    }
    for (int i = 1; i < graphSize; i++)
    {
        sizes[i] = graph[i].size();
    }

    int i, j;
    for (i = 1; i < graphSize - 1; i++)
    {
        for (j = 1; j < graphSize - i - 1; j++)
        {
            if (sizes[j] < sizes[j + 1])
            {
                swap(&sizes[j], &sizes[j + 1]);
                swap(&newGraph[j], &newGraph[j + 1]);
            }
        }
    }

    return newGraph;
}

int getMyScore(int IDX, bool A)
{
    int score = 0;
    vector<int> neighbours = graph[IDX];

    if (A)
    {
        for (int i = 0; i < neighbours.size(); i++)
        {
            //next to RED
            if (taken[neighbours[i]] == 1)
            {
                score += 2;
            }
        }
    }
    else
    {
        for (int i = 0; i < neighbours.size(); i++)
        {
            //next to RED
            if (taken[neighbours[i]] == 1)
            {
                score += 1;
            }
            //next to BLUE
            else if (taken[neighbours[i]] == 0)
            {
                score -= 1;
            }
            //free space
            else
            {
                score += 1;
            }
        }
    }

    return score;
}
int computeUpperBound()
{
    int max = 0;
    int as = As - aPlaced;
    int bs = Bs - bPlaced;
    int i = 1;

    while (i < graphSize)
    {
        if (taken[mapping[i]] == -1)
        {
            if (bs > 0)
            {
                max += graph[mapping[i]].size();
                bs--;
            }

            else if (as > 0)
            {
                max += graph[mapping[i]].size() * 2;
                as--;
            }
            else
            {
                break;
            }
        }
        i++;
    }

    return max;
}

void solve(int ags, int n, int score)
{

    if (ags == 0)
    {
        //aagnets are placed, do the same for Bagents
        if (second)
        {
            if (score > bestScore)
            {
                bestScore = score;
            }
            return;
        }
        second = true;
        solve(Bs, 1, score);
        second = false;
        return;
    }

    if ((score + computeUpperBound()) <= bestScore)
    {
        return;
    }

    if (!second)
    {
        int tmp = 0;
        for (int i = n; i < graphSize; i++)
        {
            //free place in graph
            if (taken[mapping[i]] == -1)
            {
                taken[mapping[i]] = 1;
                singleA = getMyScore(mapping[i], true);
                aPlaced++;
                solve(ags - 1, i, score + singleA);

                taken[mapping[i]] = -1;
                aPlaced--;
            }
        }
    }
    else
    {
        for (int i = n; i < graphSize; i++)
        {
            //free place in graph
            if (taken[mapping[i]] == -1)
            {
                taken[mapping[i]] = 0;
                singleB = getMyScore(mapping[i], false);
                bPlaced++;

                solve(ags - 1, i, score + singleB);
                bPlaced--;
                taken[mapping[i]] = -1;
            }
        }
    }

    //second = false;
}

vector<vector<int>> loadData()
{
    int nodes, edges;
    scanf("%d %d %d %d", &nodes, &edges, &As, &Bs);
    int cur = 0;
    int val = 0;
    vector<vector<int>> graph(nodes + 1);

    for (int i = 0; i < edges; i++)
    {
        scanf("%d %d", &cur, &val);
        graph[cur].push_back(val);
        graph[val].push_back(cur);
    }
    graphSize = graph.size();
    taken = vector<int>(graphSize, -1);
    return graph;
}

int main()
{
    int start = clock();

    bestScore = 0;
    graph = loadData();
    mapping = getSortedGraph();

    solve(As, 1, 0);
    printf("%d\n", bestScore);
    int end = clock();
    printf("It took %f seconds.\n", ((float)end - start) / CLOCKS_PER_SEC);
}