diff options
| -rw-r--r-- | 21.5/jan/gold/farm.cpp | 47 |
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'; +} |