2022 jan gold farm

1 files changed, 47 insertions, 0 deletions

diff --git a/21.5/jan/gold/farm.cpp b/21.5/jan/gold/farm.cpp
new file mode 100644
index 0000000..07354a1
--- /dev/null
+++ b/21.5/jan/gold/farm.cpp
@@ -0,0 +1,47 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+const int MX = 1e5+5;
+
+int ans[MX];
+vector<ii> E, G[MX];
+
+void dfs(int u) {
+	for (ii v : G[u]) if (ans[v.s] < min(v.f, ans[u])) {
+		ans[v.s] = min(v.f, ans[u]);
+		dfs(v.s);
+	}
+}
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	int N, Q; cin >> N >> Q;
+	fill(ans+1, ans+N+1, Q);
+	for (int i = 0; i < Q; ++i) {
+		char c; cin >> c;
+		if (c == 'D') {
+			int x; cin >> x;
+			ans[x] = i;
+		}
+		else if (c == 'A') {
+			int x, y; cin >> x >> y;
+			E.emplace_back(x, y);
+		}
+		else {
+			int e; cin >> e;
+			int u = E[e-1].f, v = E[e-1].s;
+			G[u].emplace_back(i, v), G[v].emplace_back(i, u);
+			E[e-1].f = -1;
+		}
+	}
+	for (ii & p : E) if (p.f != -1)
+		G[p.f].emplace_back(Q, p.s), G[p.s].emplace_back(Q, p.f);
+	vector<ii> vc;
+	for (int i = 1; i <= N; ++i) vc.emplace_back(ans[i], i);
+	sort(begin(vc), end(vc), greater<>());
+	for (ii & p : vc) dfs(p.s);
+	for (int i = 1; i <= N; ++i) cout << ans[i] << '\n';
+}