제출 #711179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711179		MinhAnhnd	Stranded Far From Home (BOI22_island)	C++14	0 / 100	1091 ms	9680 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>

//int 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)	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";
	}

}

컴파일 시 표준 에러 (stderr) 메시지

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;
      |                            ^~~~~

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