aboutsummaryrefslogtreecommitdiff
path: root/2018/day2/cowcliquer.cpp
diff options
context:
space:
mode:
Diffstat (limited to '2018/day2/cowcliquer.cpp')
-rw-r--r--2018/day2/cowcliquer.cpp39
1 files changed, 39 insertions, 0 deletions
diff --git a/2018/day2/cowcliquer.cpp b/2018/day2/cowcliquer.cpp
new file mode 100644
index 0000000..fc7f9e9
--- /dev/null
+++ b/2018/day2/cowcliquer.cpp
@@ -0,0 +1,39 @@
+#include "grader.h"
+#include <bits/stdc++.h>
+#define par first
+#define sz second
+using namespace std;
+using ii = pair<int, int>;
+constexpr int INF = 2e9;
+
+int cnt;
+unordered_map<string, int> s;
+vector<pair<int, ii>> m[200002];
+
+inline void alloc(string cow) { if (s.find(cow) == end(s)) s[cow] = ++cnt, m[cnt].emplace_back(0, ii(cnt, 1)); }
+
+inline ii & get(int i, int timestamp) { return prev(upper_bound(begin(m[i]), end(m[i]), make_pair(timestamp, ii(INF, 0))))->second; }
+
+int find_set(int i, int timestamp) {
+ int & p = get(i, timestamp).par;
+ return (p == i) ? i : (p = find_set(p, timestamp));
+}
+
+void add_friend(string cow1, string cow2, int timestamp) {
+ alloc(cow1), alloc(cow2);
+ int i = find_set(s[cow1], timestamp), j = find_set(s[cow2], timestamp);
+ if (i == j) return;
+ ii x = get(i, timestamp), y = get(j, timestamp);
+ if (x.sz < y.sz) swap(i, j);
+ m[i].emplace_back(timestamp, ii(i, x.sz + y.sz)), m[j].emplace_back(timestamp, ii(i, 0));
+}
+
+bool check_friend(string cow1, string cow2, int timestamp) {
+ alloc(cow1), alloc(cow2);
+ return find_set(s[cow1], timestamp) == find_set(s[cow2], timestamp);
+}
+
+int get_number_of_friends(string cow, int timestamp) {
+ alloc(cow);
+ return get(find_set(s[cow], timestamp), timestamp).sz;
+} \ No newline at end of file