Submission #1041974

#TimeUsernameProblemLanguageResultExecution timeMemory
1041974BlagojStranded Far From Home (BOI22_island)C++17
25 / 100
84 ms56568 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define all(x) (x).begin(), (x).end() const int mxn = 2e5 + 100; vector<ll> s(mxn), ldr(mxn), rnk(mxn), mx(mxn), p[mxn]; int Find(int x) { if (ldr[x] == x) return x; return ldr[x] = Find(ldr[x]); } void Union(int x, int y) { x = Find(x), y = Find(y); if (rnk[x] < mx[y]) p[x].clear(); if (rnk[y] < mx[x]) p[y].clear(); if (p[x].size() < p[y].size()) swap(x, y); for (auto el : p[y]) p[x].push_back(el); ldr[y] = x; rnk[x] += rnk[y]; mx[x] = max(mx[x], mx[y]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> s[i]; vector<pair<int, int>> edg; for (int i = 0; i < m; i++) { int f, t; cin >> f >> t; edg.push_back({f, t}); } sort(all(edg), [&] (pair<int, int> a, pair<int, int> b) { return max(s[a.first], s[a.second]) < max(s[b.first], s[b.second]); }); for (int i = 1; i <= n; i++) { ldr[i] = i; rnk[i] = s[i]; p[i] = {i}; mx[i] = s[i]; } for (auto x : edg) Union(x.first, x.second); bitset<mxn> ans; for (auto x : p[Find(1)]) ans[x] = 1; for (int i = 1; i <= n; i++) cout << ans[i]; }
#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...