#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//int R,n,m,p,totalsum = 0;
#define limit 2001
#define MAXN limit
#define Nmax limit
#define K 18
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(s) scanf("%s",s)
#define pi(x) printf("%d\n",x)
#define pl(x) printf("%lld\n",x)
#define ps(s) printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef vector<int> vi;
int mpow(int base, int exp);
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007;
struct wavelet_tree{
int lo, hi;
wavelet_tree *l, *r;
vi b;
//nos are in range [x,y]
//array indices are [from, to)
wavelet_tree(int *from, int *to, int x, int y){
lo = x, hi = y;
if(lo == hi or from >= to) return;
int mid = (lo+hi)/2;
auto f = [mid](int x){
return x <= mid;
};
b.reserve(to-from+1);
b.pb(0);
for(auto it = from; it != to; it++)
b.pb(b.back() + f(*it));
//see how lambda function is used here
auto pivot = stable_partition(from, to, f);
l = new wavelet_tree(from, pivot, lo, mid);
r = new wavelet_tree(pivot, to, mid+1, hi);
}
//kth smallest element in [l, r]
int kth(int l, int r, int k){
if(l > r) return 0;
if(lo == hi) return lo;
int inLeft = b[r] - b[l-1];
int lb = b[l-1]; //amt of nos in first (l-1) nos that go in left
int rb = b[r]; //amt of nos in first (r) nos that go in left
if(k <= inLeft) return this->l->kth(lb+1, rb , k);
return this->r->kth(l-lb, r-rb, k-inLeft);
}
//count of nos in [l, r] Less than or equal to k
int LTE(int l, int r, int k) {
if(l > r or k < lo) return 0;
if(hi <= k) return r - l + 1;
int lb = b[l-1], rb = b[r];
return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
}
//count of nos in [l, r] equal to k
int count(int l, int r, int k) {
if(l > r or k < lo or k > hi) return 0;
if(lo == hi) return r - l + 1;
int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
if(k <= mid) return this->l->count(lb+1, rb, k);
return this->r->count(l-lb, r-rb, k);
}
~wavelet_tree(){
delete l;
delete r;
}
};
int st[K + 1][MAXN];
int st2[K + 1][MAXN];
int lg[MAXN+1];
int initial_size[limit];
int current_size[limit];
int wtf_size[limit];
class UnionFind {
public:
vector<int> p,rank, setSize;
int numSets;
UnionFind(int N){
p.assign(N+1,0); for(int i = 0;i<=N;i++) p[i]= i;
rank.assign(N+1,0);
setSize.assign(N+1,0);
numSets = N;
}
int findSet(int i){
return (p[i]==i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){ return (findSet(p[i]) == findSet(p[j]));}
void unionSet(int i, int j){
if (isSameSet(i,j)) return;
int x = findSet(i); int y = findSet(j);
if(rank[x]>rank[y]) swap(x,y);
p[x] = y;
if(rank[x] == rank[y]) rank[y]++;
setSize[y] += setSize[x];
--numSets;
}
};
bool ss__(pair<int,int> a,pair<int,int> b){
long mina = max(initial_size[a.first],initial_size[a.second]);
long minb = max(initial_size[b.first],initial_size[b.second]);
return mina<minb;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N,M,B[limit],maxi = 0,maxii = 0;
int flag[limit] = {};
vector<pair<int,int>> edge;
cin>>N>>M;
for(int i = 1;i<=N;i++){
cin>>initial_size[i];
current_size[i] = initial_size[i];
wtf_size[i] = initial_size[i];
if(current_size[i]>maxi){
maxi = current_size[i];
maxii = i;
}
}
for(int i = 1;i<=M;i++){
long temp1, temp2;
cin>>temp1>>temp2;
if (initial_size[temp1]<initial_size[temp2]) swap(temp1,temp2);
edge.push_back(make_pair(temp1,temp2));
}
sort(edge.begin(),edge.end(),ss__);
UnionFind UF(N);
UnionFind UFDelta(N);
for(auto iter:edge){
int bigger = iter.first;
int smaller = iter.second;
int c = initial_size[bigger];
bigger = UF.findSet(bigger);
smaller = UF.findSet(smaller);
int a = current_size[bigger];
int b = current_size[smaller];
if(bigger==smaller) continue;
if(current_size[smaller] >= c) {
//cout<<smaller<<" "<<bigger<<" "<<current_size[smaller]<<endl;
UF.unionSet(smaller,bigger);
UFDelta.unionSet(smaller,bigger);
bigger = UF.findSet(bigger);
current_size[bigger] = a+b;
}
else{
for (long i = 1;i<=N;i++){
if (UF.findSet(i)==smaller) flag[i]=1;
}
UF.unionSet(smaller,bigger);
UFDelta.unionSet(smaller,bigger);
bigger = UF.findSet(bigger);
current_size[bigger] = a+b;
}
}
for(int i = 1;i<=N;i++){
if(!flag[i]) cout<<"1"; else cout<<"0";
}
}
Compilation message
island.cpp: In function 'int main()':
island.cpp:143:10: warning: unused variable 'B' [-Wunused-variable]
143 | int N,M,B[limit],maxi = 0,maxii = 0;
| ^
island.cpp:143:28: warning: variable 'maxii' set but not used [-Wunused-but-set-variable]
143 | int N,M,B[limit],maxi = 0,maxii = 0;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
288 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
8 ms |
1048 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
9 ms |
1108 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
8 ms |
1096 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
288 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
