#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define mt make_tuple
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(int i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10,18);
ll modulo = 1000000007;
double eps = 1e-10;
ifstream in;
ofstream out;
#define MAX 200'200
ll arr[MAX];
namespace dsu{
int aid[MAX];
vector<int> dsu[MAX];
vector<ll> good[MAX];
priority_queue<pair<int, int> , vector<pair<int, int> > , greater<pair<int, int> > > edg[MAX];
ll s[MAX];
void ini(int n){
fori(n)
aid[i] = i, dsu[i].clear(), dsu[i].push_back(i), good[i].pb(i), s[i] = arr[i];
}
ll join(int a,int b){ // 1 - if joined, 0 - if they were already joined
int aid1 = aid[a], aid2 = aid[b];
if(aid1==aid2)
return -1;
if(dsu[aid2].size() > dsu[aid1].size())
swap(aid1,aid2);
{
if(good[aid1].size() < good[aid2].size()){
swap(good[aid1], good[aid2]);
}
for(auto& el : good[aid2]){
good[aid1].pb(el);
}
}
{
if(edg[aid1].size() < edg[aid2].size()){
swap(edg[aid1], edg[aid2]);
}
while(!edg[aid2].empty()){
auto tp = edg[aid2].top();
auto hd = tp.ss;
if(aid[hd] != aid1 && aid[hd]!=aid2){
edg[aid1].push(tp);
}
edg[aid2].pop();
}
}
for(auto hd : dsu[aid2]){
aid[hd] = aid1;
dsu[aid1].push_back(hd);
}
dsu[aid2].clear();
good[aid2].clear();
s[aid1]+=s[aid2];
return aid1;
}
};
using namespace dsu;
void deal(){
ll n, m;
cin>>n>>m;
fori(n){
cin>>arr[i];
}
ini(n);
fori(m){
ll ai, bi;
cin>>ai>>bi;
--ai, --bi;
edg[ai].push(mp(arr[bi], bi));
edg[bi].push(mp(arr[ai], ai));
}
set<pair<ll, ll> > all; // components and their sizes
fori(n){
all.insert(mp(arr[i], i));
}
while((ll)all.size() > 1){
auto it = all.begin();
ll hd = (*it).ss;
all.erase(all.begin());
while(1){
assert(!edg[hd].empty());
auto it = edg[hd].top();
edg[hd].pop();
ll wh = it.ss;
if(aid[wh] == hd){
continue;
}
else{
if(s[hd] >= arr[wh]){
ll hr = aid[wh];
assert(all.find(mp(s[hr], hr) )!=all.end());
all.erase(mp(s[hr], hr));
ll cr = join(hd, hr);
all.insert(mp(s[cr], cr));
}
else{
good[hd].clear();
}
break;
}
}
}
ll cr = aid[0];
vector<bool> ans(n, 0);
for(auto& el : good[cr]){
ans[el] = 1;
}
fori(n){
cout<<ans[i];
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
deal();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 2 |
Runtime error |
27 ms |
32244 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
32300 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15924 KB |
Output is correct |
| 2 |
Runtime error |
230 ms |
103148 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15972 KB |
Output is correct |
| 2 |
Runtime error |
232 ms |
105436 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 2 |
Runtime error |
27 ms |
32244 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
