Submission #1095485

#TimeUsernameProblemLanguageResultExecution timeMemory
1095485duckindogStranded Far From Home (BOI22_island)C++17
100 / 100
99 ms29036 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, m; int a[N]; vector<pair<int, int>> edges; long long total[N]; int id[N]; vector<int> vt[N]; bool mk[N]; int root(int u) { return id[u] < 0 ? u : root(id[u]); } void add(int u, int v) { u = root(u); v = root(v); if (u == v) return; if (a[u] < a[v]) swap(u, v); if (total[v] < a[u]) { for (const auto& x : vt[v]) mk[x] = false; vt[v].clear(); } if (id[u] > id[v]) swap(u, v); total[u] += total[v]; a[u] = max(a[u], a[v]); vt[u].insert(vt[u].end(), vt[v].begin(), vt[v].end()); id[u] += id[v]; id[v] = u; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; edges.push_back({u, v}); } sort(edges.begin(), edges.end(), [&](const auto& x, const auto& y) { return max(a[get<0>(x)], a[get<1>(x)]) < max(a[get<0>(y)], a[get<1>(y)]); }); for (int i = 1; i <= n; ++i) { total[i] = a[i]; vt[i] = {i}; } memset(mk, true, sizeof mk); memset(id, -1, sizeof id); for (const auto& [u, v] : edges) add(u, v); for (int i = 1; i <= n; ++i) cout << mk[i]; cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...