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;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
vector<pair<int, int>> e;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
e.emplace_back(u, v);
}
sort(e.begin(), e.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
return max(s[a.first], s[a.second]) < max(s[b.first], s[b.second]);
});
vector<int> p(n), mx(n);
vector<i64> sum(n);
vector<vector<int>> win(n);
for (int i = 0; i < n; i++) {
p[i] = i;
mx[i] = sum[i] = s[i];
win[i] = {i};
}
auto leader = [&](int u) {
while (u != p[u]) u = p[u] = p[p[u]];
return u;
};
auto unite = [&](int u, int v) {
u = leader(u);
v = leader(v);
if (u == v)
return;
if (sum[u] < mx[v])
win[u].clear();
if (sum[v] < mx[u])
win[v].clear();
if (win[u].size() < win[v].size())
swap(u, v);
win[u].insert(win[u].end(), win[v].begin(), win[v].end());
win[v].clear();
sum[u] += sum[v];
mx[u] = max(mx[u], mx[v]);
p[v] = u;
};
for (auto [u, v] : e) {
unite(u, v);
}
vector<int> ans(n);
for (int u : win[leader(0)]) {
ans[u] = 1;
}
for (int i = 0; i < n; i++) {
cout << ans[i];
}
cout << "\n";
return 0;
}
# | 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... |