#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, m, a[N], par[N];
ll sm[N];
vector<int> g[N], vals;
vector<pair<int, pair<int, int>>> edges;
set<int> alive[N];
int root(int v){
return (par[v] == -1 ? v : par[v] = root(par[v]));
}
void merge(int u, int v, int w){
if ((u = root(u)) == (v = root(v)))
return ;
if (sm[u] < w)
alive[u].clear();
if (sm[v] < w)
alive[v].clear();
if (alive[u].size() > alive[v].size())
swap(u, v);
par[u] = v;
sm[v] += sm[u];
for (int x : alive[u])
alive[v].insert(x);
alive[u].clear();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> a[i], vals.push_back(a[i]), par[i] = -1, sm[i] = a[i], alive[i].insert(i);
for (int i = 0; i < m; i ++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({max(a[u], a[v]), {u, v}});
}
sort(edges.begin(), edges.end());
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
for (auto [w, E] : edges){
auto [u, v] = E;
merge(u, v, w);
}
for (int v = 1; v <= n; v ++){
if (alive[root(v)].find(v) == alive[root(v)].end())
cout << '0';
else
cout << '1';
}
cout << endl;
}
# | 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... |