제출 #648238

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

island

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll cc[200001];
ll siz[200001];
ll sizes[200001];
vector<ll> stuff[200001];
ll ans[200001];
vector<vector<ll>> edges;

ll n,m;
int find(ll a){
	while (cc[a] != a){
		cc[a] = cc[cc[a]];
		a = cc[a];
	}
	return a;
}

void unite(ll a,ll b){
	ll aa = find(a);
	ll bb = find(b);
	if (aa==bb) return;

	if (siz[aa] < sizes[b]){
		for (auto&i : stuff[aa]){
			ans[i] = 0;
		}
		stuff[aa] = {};
	}
	if (siz[bb] < sizes[a]){
		for (auto&i : stuff[bb]){
			ans[i] = 0;
		}
		stuff[bb] = {};
	}

	if (stuff[aa].size() > stuff[bb].size()){
		swap(stuff[aa], stuff[bb]);
	}
	for (auto&i : stuff[aa]){
		stuff[bb].push_back(i);
	}

	siz[bb] += siz[aa];
	cc[aa] = bb;
}

int main(){
	cin >> n >> m;
	FOR(i,0,n){
		cc[i] = i;
		cin >> sizes[i];
		siz[i] = sizes[i];
		stuff[i].push_back(i);
		ans[i] = 1;
	}

	FOR(i,0,m){
		ll a,b;
		cin >> a >> b;
		a--;b--;
		edges.push_back({max(sizes[a],sizes[b]), a,b});
	}

	sort(edges.begin(), edges.end());

	for (auto&i : edges){
		unite(i[1],i[2]);
	}
	FOR(i,0,n) cout << ans[i];


}

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