#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
ll a[200005];
int par[200005];
ll sum[200005];
vector<int>comp[200005];
ll mx[200005];
int n,m;
int cash;
bool cmp(pair<int,int>l,pair<int,int>r){
if(a[l.fr]==a[r.fr])return a[l.sc]<a[r.sc];
return a[l.fr]<a[r.fr];
}
int fin(int v){return (v==par[v])?v:par[v]=fin(par[v]);}
void unite(int a,int b){
a=fin(a);
b=fin(b);
if(a==b)return;
if(comp[a].size()<comp[b].size())swap(a,b);
if(sum[a]<mx[b])comp[a].clear();
if(sum[b]<mx[a])comp[b].clear();
par[b]=a;
umax(mx[a],mx[b]);
sum[a]+=sum[b];
cash=a;
for(int to:comp[b])comp[a].push_back(to);
comp[b].clear();
}
int ans[200005];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
mx[i]=a[i];
sum[i]=a[i];
comp[i].push_back(i);
par[i]=i;
}
vector<pair<pair<ll,ll>,pair<int,int>>>edges;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(a[x]<a[y])swap(x,y);
edges.push_back(make_pair(make_pair(a[x],a[y]),make_pair(x,y)));
}
sort(edges.begin(),edges.end());
for(int i=1;i<=m;i++)unite(edges[i-1].sc.fr,edges[i-1].sc.sc);
for(int to:comp[cash])ans[to]=1;
for(int i=1;i<=n;i++)printf("%d",ans[i]);
}
Compilation message
island.cpp: In function 'int main()':
island.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
island.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%lld",&a[i]);
| ~~~~~^~~~~~~~~~~~~~
island.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
