diff options
| -rw-r--r-- | Sources/DataStructure.cpp | 271 |
1 files changed, 163 insertions, 108 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index 2c444df..07f8b43 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,135 +1,190 @@ -#include <cstdio> -#include <cstdlib> -#include <vector> -#include <algorithm> #include <iostream> -//#include <gtest/gtest.h> +#include <vector> +#include <string> -using std::cin; -using std::cout; -using std::endl; -using std::max; +using std::string; using std::vector; +using std::cin; -struct Table { - int numberOfRows; - int setID; - - Table(int numberOfRows, int setID) : - numberOfRows(numberOfRows), setID(setID) { - } +struct Query { + string type, name; + int number; }; -int maximumNumberOfRows = -1; -vector<int> parent; -vector<int> rank; -vector<Table> tables; - -int find(int i) { - if (i != parent[i]) - parent[i] = find(parent[i]); - return parent[i]; +vector<Query> read_queries() { + int n; + cin >> n; + vector<Query> queries(n); + for (int i = 0; i < n; ++i) { + cin >> queries[i].type; + if (queries[i].type == "add") + cin >> queries[i].number >> queries[i].name; + else + cin >> queries[i].number; + } + return queries; } -void unite(int destination, int source) { - int destination_id = find(destination); - int source_id = find(source); - if (destination_id == source_id) - return; - if (rank[destination_id] > rank[source_id]) - parent[source_id] = destination_id; - else { - parent[destination_id] = source_id; - if (rank[destination_id] == rank[source_id]) - rank[source_id] = rank[source_id] + 1; - } +void write_responses(const vector<string>& result) { + for (size_t i = 0; i < result.size(); ++i) + std::cout << result[i] << "\n"; } -void merge(int destination, int source) { - int d = find(destination); - int s = find(source); - Table* realDestination = &tables[d]; - Table* realSource = &tables[s]; - if (d == s) { - return; - } - maximumNumberOfRows = max(maximumNumberOfRows, - tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows); - realDestination->numberOfRows = tables[realDestination->setID].numberOfRows - + tables[realSource->setID].numberOfRows; - realSource->numberOfRows = 0; - realSource->setID = d; - realDestination->setID = d; - unite(destination, source); +vector<string> process_queries(const vector<Query>& queries) { + vector<string> result; + // Keep list of all existing (i.e. not deleted yet) contacts. + vector<string> contacts(10000000); + for (size_t i = 0; i < contacts.size(); i++) { + contacts[i] = "not found"; + } + for (size_t i = 0; i < queries.size(); ++i) + if (queries[i].type == "add") { + contacts[queries[i].number] = queries[i].name; + } else if (queries[i].type == "del") { + contacts[queries[i].number] = "not found"; + } else { + result.push_back(contacts[queries[i].number]); + } + return result; } int main() { - int n, m; - cin >> n >> m; - - parent.resize(n); - rank.resize(n); -// tables.resize(n); - for (int i = 0; i < n; i++) { - int numberOfRows; - cin >> numberOfRows; - tables.push_back(Table(numberOfRows, i)); -// tables[i] = Table(numberOfRows, i); - parent[i] = i; - rank[i] = 0; - maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows); - } - - for (int i = 0; i < m; i++) { - int destination, source; - cin >> destination >> source; - --destination; - --source; - - merge(destination, source); - cout << maximumNumberOfRows << endl; - } - - return 0; + write_responses(process_queries(read_queries())); + return 0; } -//TEST(MergingTables, t) { -// maximumNumberOfRows = 1; -// rank = {0, 0, 0, 0, 0}; -// parent = {0, 1, 2, 3, 4}; -// tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)}; +//#include <cstdio> +//#include <cstdlib> +//#include <vector> +//#include <algorithm> +//#include <iostream> +////#include <gtest/gtest.h> // -// merge(2, 4); -// ASSERT_EQ(2, maximumNumberOfRows); +//using std::cin; +//using std::cout; +//using std::endl; +//using std::max; +//using std::vector; // -// merge(1, 3); -// ASSERT_EQ(2, maximumNumberOfRows); +//struct Table { +// int numberOfRows; +// int setID; // -// merge(0, 3); -// ASSERT_EQ(3, maximumNumberOfRows); +// Table(int numberOfRows, int setID) : +// numberOfRows(numberOfRows), setID(setID) { +// } +//}; // -// merge(4, 3); -// ASSERT_EQ(5, maximumNumberOfRows); +//int maximumNumberOfRows = -1; +//vector<int> parent; +//vector<int> rank; +//vector<Table> tables; // -// merge(4, 2); -// ASSERT_EQ(5, maximumNumberOfRows); +//int find(int i) { +// if (i != parent[i]) +// parent[i] = find(parent[i]); +// return parent[i]; //} // -//TEST(MergingTables, t1) { -// maximumNumberOfRows = 10; -// rank = {0, 0, 0, 0, 0, 0}; -// parent = {0, 1, 2, 3, 4, 5}; -// tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)}; +//void unite(int destination, int source) { +// int destination_id = find(destination); +// int source_id = find(source); +// if (destination_id == source_id) +// return; +// if (rank[destination_id] > rank[source_id]) +// parent[source_id] = destination_id; +// else { +// parent[destination_id] = source_id; +// if (rank[destination_id] == rank[source_id]) +// rank[source_id] = rank[source_id] + 1; +// } +//} // -// merge(5, 5); -// ASSERT_EQ(10, maximumNumberOfRows); +//void merge(int destination, int source) { +// int d = find(destination); +// int s = find(source); +// Table* realDestination = &tables[d]; +// Table* realSource = &tables[s]; +// if (d == s) { +// return; +// } +// maximumNumberOfRows = max(maximumNumberOfRows, +// tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows); +// realDestination->numberOfRows = tables[realDestination->setID].numberOfRows +// + tables[realSource->setID].numberOfRows; +// realSource->numberOfRows = 0; +// realSource->setID = d; +// realDestination->setID = d; +// unite(destination, source); +//} // -// merge(5, 4); -// ASSERT_EQ(10, maximumNumberOfRows); +//int main() { +// int n, m; +// cin >> n >> m; // -// merge(4, 3); -// ASSERT_EQ(10, maximumNumberOfRows); +// parent.resize(n); +// rank.resize(n); +//// tables.resize(n); +// for (int i = 0; i < n; i++) { +// int numberOfRows; +// cin >> numberOfRows; +// tables.push_back(Table(numberOfRows, i)); +//// tables[i] = Table(numberOfRows, i); +// parent[i] = i; +// rank[i] = 0; +// maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows); +// } // -// merge(3, 2); -// ASSERT_EQ(11, maximumNumberOfRows); +// for (int i = 0; i < m; i++) { +// int destination, source; +// cin >> destination >> source; +// --destination; +// --source; +// +// merge(destination, source); +// cout << maximumNumberOfRows << endl; +// } +// +// return 0; //} +// +////TEST(MergingTables, t) { +//// maximumNumberOfRows = 1; +//// rank = {0, 0, 0, 0, 0}; +//// parent = {0, 1, 2, 3, 4}; +//// tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)}; +//// +//// merge(2, 4); +//// ASSERT_EQ(2, maximumNumberOfRows); +//// +//// merge(1, 3); +//// ASSERT_EQ(2, maximumNumberOfRows); +//// +//// merge(0, 3); +//// ASSERT_EQ(3, maximumNumberOfRows); +//// +//// merge(4, 3); +//// ASSERT_EQ(5, maximumNumberOfRows); +//// +//// merge(4, 2); +//// ASSERT_EQ(5, maximumNumberOfRows); +////} +//// +////TEST(MergingTables, t1) { +//// maximumNumberOfRows = 10; +//// rank = {0, 0, 0, 0, 0, 0}; +//// parent = {0, 1, 2, 3, 4, 5}; +//// tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)}; +//// +//// merge(5, 5); +//// ASSERT_EQ(10, maximumNumberOfRows); +//// +//// merge(5, 4); +//// ASSERT_EQ(10, maximumNumberOfRows); +//// +//// merge(4, 3); +//// ASSERT_EQ(10, maximumNumberOfRows); +//// +//// merge(3, 2); +//// ASSERT_EQ(11, maximumNumberOfRows); +////} |