Submission #711188

#	Time	Username	Problem	Language	Result	Execution time	Memory
711188		MinhAnhnd	Stranded Far From Home (BOI22_island)	C++14	100 / 100	345 ms	79612 KiB

island

#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>

//long R,n,m,p,totalsum = 0;
#define limit 200001
#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)	prlongf("%d\n",x)
#define pl(x)	prlongf("%lld\n",x)
#define ps(s)	prlongf("%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<long>		vi;

long mpow(long base, long exp);
void ipgraph(long m);
void dfs(long u, long par);
const long mod = 1000000007;




struct wavelet_tree{
	long lo, hi;
	wavelet_tree *l, *r;
	vi b;

	//nos are in range [x,y]
	//array indices are [from, to)
	wavelet_tree(long *from, long *to, long x, long y){
		lo = x, hi = y;
		if(lo == hi or from >= to) return;
		long mid = (lo+hi)/2;
		auto f = [mid](long 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]
	long kth(long l, long r, long k){
		if(l > r) return 0;
		if(lo == hi) return lo;
		long inLeft = b[r] - b[l-1];
		long lb = b[l-1]; //amt of nos in first (l-1) nos that go in left
		long 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
	long LTE(long l, long r, long k) {
		if(l > r or k < lo) return 0;
		if(hi <= k) return r - l + 1;
		long 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
	long count(long l, long r, long k) {
		if(l > r or k < lo or k > hi) return 0;
		if(lo == hi) return r - l + 1;
		long 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;
	}
};

long st[K + 1][MAXN];
long st2[K + 1][MAXN];
long lg[MAXN+1];
long initial_size[limit];
long current_size[limit];
long wtf_size[limit];
class UnionFind {
    public:
    vector<long> p,rank, setSize;
    vector<long> inside[limit];
    long numSets;
    UnionFind(long N){
        p.assign(N+1,0); for(long i = 0;i<=N;i++) {p[i]= i; inside[i].push_back(i);}
        rank.assign(N+1,0);
        setSize.assign(N+1,0);

        numSets = N;
    }
    long findSet(long i){
        return (p[i]==i) ? i : (p[i] = findSet(p[i]));
    }
    bool isSameSet(long i, long j){ return (findSet(p[i]) == findSet(p[j]));}
    void unionSet(long i, long j){
        if (isSameSet(i,j)) return;
        long x = findSet(i); long y = findSet(j);
        if(rank[x]>rank[y]) swap(x,y);
        p[x] = y;
        for(auto a: inside[x]) inside[y].push_back(a);
        if(rank[x] == rank[y]) rank[y]++;
        setSize[y] += setSize[x];
        --numSets;
    }
};

bool ss__(pair<long,long> a,pair<long,long> 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);
	long N,M,B[limit],maxi = 0,maxii = 0;
	long flag[limit] = {};

	vector<pair<long,long>> edge;
	cin>>N>>M;
	for(long 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(long 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){
        long bigger = iter.first;
        long smaller = iter.second;
        long c = initial_size[bigger];
        bigger = UF.findSet(bigger);
        smaller = UF.findSet(smaller);
        long a = current_size[bigger];
        long 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 (auto i:UF.inside[smaller]){
                 flag[i]=1;
            }

            UF.unionSet(smaller,bigger);

            UFDelta.unionSet(smaller,bigger);

            bigger = UF.findSet(bigger);
            current_size[bigger] = a+b;
        }
	}

	for(long i = 1;i<=N;i++){
        if(!flag[i]) cout<<"1"; else cout<<"0";
	}

}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:146:11: warning: unused variable 'B' [-Wunused-variable]
  146 |  long N,M,B[limit],maxi = 0,maxii = 0;
      |           ^
island.cpp:146:29: warning: variable 'maxii' set but not used [-Wunused-but-set-variable]
  146 |  long N,M,B[limit],maxi = 0,maxii = 0;
      |                             ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35