제출 #999649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999649		pcc	Stranded Far From Home (BOI22_island)	C++17	100 / 100	264 ms	56264 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
bitset<mxn> done;
vector<int> paths[mxn];
vector<int> tree[mxn];
int N,M;
int arr[mxn];
bitset<mxn> ans;

struct DSU{
	int dsu[mxn];
	ll sum[mxn];
	priority_queue<pii,vector<pii>,greater<pii>> pq[mxn];
	void init(int n){
		for(int i = 0;i<n;i++)dsu[i] = i;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(pq[a].size()<pq[b].size())swap(a,b);
		while(!pq[b].empty()){
			pq[a].push(pq[b].top());
			pq[b].pop();
		}
		sum[a] += sum[b];
		dsu[b] = a;
		return;
	}
};
DSU dsu;

void dfs(int now){
	ans[now] = 1;
	for(auto nxt:tree[now]){
		if(!ans[nxt]){
			dfs(nxt);
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	vector<int> perm;
	for(int i = 1;i<=N;i++)cin>>arr[i],dsu.sum[i] = arr[i],perm.push_back(i);
	sort(perm.begin(),perm.end(),[](int a,int b){return arr[a]<arr[b];});
	dsu.init(mxn);
	for(int i = 1;i<=M;i++){
		int a,b;
		cin>>a>>b;
		paths[a].push_back(b);
		paths[b].push_back(a);
		dsu.pq[a].push(pii(arr[b],b));
		dsu.pq[b].push(pii(arr[a],a));
	}
	for(auto now:perm){
		done[now] = true;
		for(auto nxt:paths[now]){
			if(done[nxt])dsu.onion(now,nxt);
		}
		int rt = dsu.root(now);
		while(!dsu.pq[rt].empty()&&done[dsu.pq[rt].top().sc])dsu.pq[rt].pop();
		if(!dsu.pq[rt].empty()&&dsu.pq[rt].top().fs<=dsu.sum[rt])tree[dsu.pq[rt].top().sc].push_back(now);
	}
	dfs(perm.back());
	for(int i = 1;i<=N;i++)cout<<ans[i];
	return 0;
}

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