summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Sources/DataStructure.cpp271
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);
+////}