Submission #987304

#TimeUsernameProblemLanguageResultExecution timeMemory
987304batsukh2006Stranded Far From Home (BOI22_island)C++11
100 / 100
222 ms52828 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int N = 2e5 + 69; #define int long long int n, m, a[N], p[N], sz[N], sum[N], vis[N], ans[N]; vector<int> g[N], can[N]; int root(int v) { if (p[v] == v) return v; return p[v] = root(p[v]); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while (tt--) { cin >> n >> m; for (int i = 1;i <= n;i++) { cin >> a[i]; p[i] = i, sz[i] = 1; sum[i] = a[i]; can[i].push_back(i); } vector<tuple<int, int, int>> edges; for (int i = 1;i <= m;i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); int c = max(a[x], a[y]); edges.push_back({c, x, y}); } sort(edges.begin(), edges.end()); for (auto u : edges) { int a1, b1, c; tie(c, a1, b1) = u; int x = root(a1); int y = root(b1); assert(sum[x] >= a[a1] && sum[y] >= a[b1]); if (x != y) { if (sum[x] >= c && sum[y] >= c) { if (sz[x] < sz[y]) swap(x, y); for (auto j : can[y]) can[x].push_back(j); } else { if (sum[x] < sum[y]) swap(x, y); } p[y] = x; sz[x] += sz[y]; sum[x] += sum[y]; } } // int ok = 1; // for (int i = 2;i <= n;i++) // ok &= (root(i) == root(i - 1)); // assert(ok); for (auto j : can[root(1)]) ans[j] = 1; for (int i = 1;i <= n;i++) cout << ans[i]; cout << '\n'; } return 0; }
#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...