UVa 12096

The SetStack Computer.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <stack>
#include <string>

using namespace std;

int totalID = 1;
stack<int> Stack;
map<int, set<int>> idMappingTable;
map<set<int>, int> contentsMappingTable;

int popTopElement()
{
	auto topElement = Stack.top();
	Stack.pop();
	return topElement;
}

void pushToStackWith(set<int> &contents)
{
	if (contentsMappingTable.count(contents))
	{
		Stack.push(contentsMappingTable[contents]);
	}
	else
	{
		Stack.push(totalID);
		contentsMappingTable[contents] = totalID;
		idMappingTable[totalID++] = contents;
	}
}

void init()
{
	totalID = 1;
	Stack = stack<int> {};
	idMappingTable.clear();
	contentsMappingTable.clear();
	idMappingTable[0] = set<int> {};
	contentsMappingTable[set<int> {}] = 0;
}

void addOperation(int firstItemID, int secondItemID)
{
	auto secondItemContents = idMappingTable[secondItemID];
	secondItemContents.insert(firstItemID);
	pushToStackWith(secondItemContents);
}

void unionOperation(int firstItemID, int secondItemID)
{
	auto unionSet = set<int> {};
	set_union(idMappingTable[firstItemID].begin(), idMappingTable[firstItemID].end(), idMappingTable[secondItemID].begin(),
			  idMappingTable[secondItemID].end(), inserter(unionSet, unionSet.begin()));
	pushToStackWith(unionSet);
}

void intersectOperation(int firstItemID, int secondItemID)
{
	auto intersectSet = set<int> {};
	set_intersection(idMappingTable[firstItemID].begin(), idMappingTable[firstItemID].end(), idMappingTable[secondItemID].begin(),
					 idMappingTable[secondItemID].end(), inserter(intersectSet, intersectSet.begin()));
	pushToStackWith(intersectSet);
}

int main()
{
	auto T = 0, N = 0;
	scanf("%d", &T);
	for (auto i = 0; i < T; i++)
	{
		init();
		scanf("%d", &N);
		for (auto j = 0; j < N; j++)
		{
			auto operationText = string {};
			cin >> operationText;
			if (operationText == "PUSH")
			{
				Stack.push(0);
			}
			else if (operationText == "DUP")
			{
				Stack.push(Stack.top());
			}
			else
			{
				auto firstItemID = popTopElement();
				auto secondItemID = popTopElement();
				if (operationText == "ADD")
				{
					addOperation(firstItemID, secondItemID);
				}
				else if (operationText == "UNION")
				{
					unionOperation(firstItemID, secondItemID);
				}
				else if (operationText == "INTERSECT")
				{
					intersectOperation(firstItemID, secondItemID);
				}
			}

			printf("%d\n", idMappingTable[Stack.top()].size());
		}
		printf("***\n");
	}
	return 0;
}