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;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'
const int LIM = 2e5;
int N, M, s[LIM], e[LIM];
vector<int> g[LIM], h[LIM];
int find(int u) {
return e[u] < 0 ? u : e[u] = find(e[u]);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
array<int, 2> byS[N];
for(int i = 0; i < N; ++i) {
cin >> s[i];
e[i] = -1;
h[i] = {i};
byS[i] = {s[i], i};
}
for(int i = 0; i < M; ++i) {
int u, v; cin >> u >> v;
--u, --v;
if(make_pair(s[u], u) < make_pair(s[v], v)) swap(u, v);
g[u].push_back(v);
}
sort(byS, byS + N);
for(auto [_, r] : byS) {
int u = find(r);
for(int &v : g[r]) {
v = find(v);
if(s[v] < s[u]) h[v].clear();
if(size(h[v]) > size(h[u]))
h[u].swap(h[v]);
}
for(int &v : g[r]) if(u != v) {
for(int y : h[v]) h[u].push_back(y);
s[u] += s[v];
e[v] = u;
}
}
for(int u : h[find(0)])
s[u] = -1;
for(int i = 0; i < N; ++i)
cout << (s[i] < 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... |