#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>link[200100];
vector<pair<int,int>>x;
int uf[200100];
int sum[200100];
int mi[200100];
int cnt[200100];
int f(int n)
{
if(uf[n]==n)
return n;
return uf[n]=f(uf[n]);
}
void u(int n,int m)
{
n=f(n);
m=f(m);
if(n==m)
return;
sum[n]+=sum[m];
if(mi[n]==mi[m])
cnt[n]+=cnt[m];
else if(mi[n]>mi[m])
{
mi[n]=mi[m];
cnt[n]=cnt[m];
}
uf[m]=n;
}
vector<int>carry;
int arr[200100];
int ans[200100];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,M;
cin >>N>>M;
int i;
for(i=0;i<N;i++)
cin >>arr[i+1];
for(i=0;i<M;i++)
{
int a,b;
cin >>a>>b;
link[a].push_back(b);
link[b].push_back(a);
x.push_back({a,b});
}
int summ=0;
vector<pair<int,int>>t;
for(i=0;i<N;i++)
{
summ+=arr[i+1];
t.push_back({arr[i+1],i+1});
carry.push_back(i+1);
}
sort(t.begin(),t.end());
for(i=0;i<32;i++)
{
int ve=(1LL<<i);
int i;
memset(uf,-1,sizeof(uf));
memset(sum,0,sizeof(sum));
memset(mi,10,sizeof(mi));
memset(cnt,0,sizeof(cnt));
for(i=0;i<N;i++)
{
if(t[i].first<ve)
{
uf[t[i].second]=t[i].second;
sum[t[i].second]=t[i].first;
int j;
for(j=0;j<link[t[i].second].size();j++)
{
if(uf[link[t[i].second][j]]>=0)
{
u(link[t[i].second][j],t[i].second);
}
}
}
else
{
vector<int>arrr;
int j;
for(j=0;j<link[t[i].second].size();j++)
{
if(uf[link[t[i].second][j]]>=0)
{
arrr.push_back(f(link[t[i].second][j]));
}
}
sort(arrr.begin(),arrr.end());
arrr.erase(unique(arrr.begin(),arrr.end()),arrr.end());
for(j=0;j<arrr.size();j++)
{
if(mi[arrr[j]]==t[i].first)
cnt[arrr[j]]++;
else if(mi[arrr[j]]>t[i].first)
{
mi[arrr[j]]=t[i].first;
cnt[arrr[j]]=1;
}
}
}
}
vector<int>nc;
for(i=0;i<carry.size();i++)
{
if(arr[carry[i]]<ve)
{
int v=sum[f(carry[i])];
if(mi[f(carry[i])]<=v)
v+=mi[f(carry[i])];
if(v>=summ)
ans[carry[i]]=1;
else if(v>=2*ve)
{
nc.push_back(carry[i]);
}
}
else
{
int v=arr[carry[i]];
int ma=1LL<<60;
int j;
vector<int>arrr;
for(j=0;j<link[carry[i]].size();j++)
{
if(uf[link[carry[i]][j]]>=0)
arrr.push_back(f(link[carry[i]][j]));
else
arrr.push_back(link[carry[i]][j]);
}
sort(arrr.begin(),arrr.end());
arrr.erase(unique(arrr.begin(),arrr.end()),arrr.end());
for(j=0;j<arrr.size();j++)
{
if(uf[arrr[j]]>=0)
{
if(mi[arrr[j]]!=arr[carry[i]]||cnt[arrr[j]]!=1)
ma=min(ma,mi[arrr[j]]);
v+=sum[arrr[j]];
}
else
{
ma=min(ma,arr[arrr[j]]);
}
}
if(ma<=v)
v+=ma;
if(v>=summ)
ans[carry[i]]=1;
else if(v>=2*ve)
{
nc.push_back(carry[i]);
}
}
}
carry=nc;
}
for(i=1;i<=N;i++)
cout <<ans[i];
}
Compilation message
island.cpp: In function 'int main()':
island.cpp:76:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(j=0;j<link[t[i].second].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:88:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(j=0;j<link[t[i].second].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:98:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(j=0;j<arrr.size();j++)
| ~^~~~~~~~~~~~
island.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(i=0;i<carry.size();i++)
| ~^~~~~~~~~~~~~
island.cpp:131:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(j=0;j<link[carry[i]].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~~~
island.cpp:140:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(j=0;j<arrr.size();j++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
11212 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11296 KB |
Output is correct |
| 3 |
Correct |
13 ms |
11248 KB |
Output is correct |
| 4 |
Incorrect |
22 ms |
11476 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11292 KB |
Output is correct |
| 2 |
Correct |
13 ms |
11220 KB |
Output is correct |
| 3 |
Execution timed out |
1074 ms |
32012 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
11220 KB |
Output is correct |
| 2 |
Execution timed out |
1075 ms |
31960 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
11412 KB |
Output is correct |
| 2 |
Execution timed out |
1085 ms |
32008 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
11212 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11296 KB |
Output is correct |
| 3 |
Correct |
13 ms |
11248 KB |
Output is correct |
| 4 |
Incorrect |
22 ms |
11476 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
