#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<long long> e;
DSU(long long N) { e = vector<long long>(N, -1); }
long long get(long long x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(long long a, long long b) { return get(a) == get(b); }
long long size(long long x) { return -e[get(x)]; }
bool unite(long long x, long long y, vector<long long> &strength) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
strength[x] += strength[y];
}
};
void dfs(long long u, long long works, vector<long long> &winnable, vector<vector<long long> > &val){
winnable[u] &= works;
for(long long v : val[u]){
dfs(v, winnable[u], winnable, val);
}
}
long long main(){
long long n, m;
cin >> n >> m;
long long arr[n];
for(long long i = 0; i < n; i++){
cin >> arr[i];
}
vector<long long> adj[n];
for(long long i = 0; i < m; i++){
long long a, b;
cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
DSU dsu(n);
vector<long long> winnable(n, 1);
vector<bool> visited(n, false);
vector<long long> inserted(n);
vector<long long> comp(n);
vector<long long> strength(n);
vector<vector<long long> > mark(n);
vector<pair<long long, long long> > order(n);
for(long long i = 0; i < n; i++){
strength[i] = arr[i];
order[i] = make_pair(arr[i], i);
}
sort(order.begin(), order.end());
for(auto t : order){
long long u = t.second;
for(long long v : adj[u]){
if(inserted[v]){
long long w = comp[dsu.get(v)];
if(strength[dsu.get(v)] < arr[u]){
winnable[w] = 0;
}
if(!visited[w]){
mark[u].push_back(w);
visited[w] = true;
}
}
}
for(long long v : adj[u]){
if(inserted[v]){
visited[comp[dsu.get(v)]] = 0;
}
}
for(long long v : adj[u]){
if(inserted[v]){
dsu.unite(u, v, strength);
}
}
comp[dsu.get(u)] = u;
inserted[u] = 1;
}
dfs(order[n - 1].second, 1, winnable, mark);
for(long long i = 0; i < n; i++){
cout << winnable[i];
}
cout << "\n";
}
Compilation message
cc1plus: error: '::main' must return 'int'
