This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |