//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/5;
const ll mod = 998244353;
#define bit(x,y) ((x >> y) & 1LL)
ll b[N];
vector<ll> a[N];
ll p[N],sz[N];
vector<ll> sus[N];
ll ans[N],id[N];
ll cmp(ll x, ll y)
{
return b[x] < b[y];
}
ll fp(ll x)
{
if(p[x] == 0) return x;
else
{
p[x] = fp(p[x]);
return p[x];
}
}
void hop(ll x, ll y)
{
x = fp(x);
y = fp(y);
if(x == y) return;
if(sus[x].size() < sus[y].size()) swap(x,y);
p[y] = x;
sz[x] += sz[y];
while(sus[y].size() > 0)
{
sus[x].push_back(sus[y].back());
sus[y].pop_back();
}
}
int main()
{
ll n,m;
cin >> n >> m;
ll i,j;
vector<ll> c;
for(i = 1;i <= n;i++)
{
p[i] = 0;
c.push_back(i);
cin >> b[i];
sz[i] = b[i];
sus[i].push_back(i);
}
for(i = 1;i <= m;i++)
{
ll x,y;
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
sort(c.begin(),c.end(),cmp);
for(i = 0;i < c.size();i++)
{
id[c[i]] = i;
}
for(auto x : c)
{
for(auto y : a[x])
{
if(id[y] > id[x]) continue;
if(sz[fp(y)] < b[x])
{
sus[fp(y)].clear();
}
hop(x,y);
}
}
ll r = fp(1);
for(auto x : sus[r]) ans[x] = 1;
for(i = 1;i <= n;i++) cout << ans[i];
}
# | 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... |