Submission #710930

#	Time	Username	Problem	Language	Result	Execution time	Memory
710930		emptypringlescan	Stranded Far From Home (BOI22_island)	C++17	25 / 100	266 ms	70180 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long
int par[200005];
long long men[200005];
vector<int> sz[200005];
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
void merge(int x, int y){
	x=find(x); y=find(y);
	assert(x<200005&&y<200005);
	if(sz[x].size()<=sz[y].size()){
		for(int i:sz[x]) sz[y].push_back(i);
		sz[x].clear();
	}
	else{
		for(int i:sz[y]) sz[x].push_back(i);
		swap(sz[x],sz[y]);
		sz[x].clear();
	}
	men[y]+=men[x];
	men[x]=0;
	par[x]=y;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=0; i<200005; i++) par[i]=i;
	int n,m;
	cin >> n >> m;
	pair<long long,int> arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i].first;
		arr[i].second=i;
	}
	sort(arr,arr+n);
	vector<int> adj[n];
	for(int i=0; i<m; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int ans[n],on[n];
	for(int i=0; i<n; i++){
		ans[i]=1;
		on[i]=0;
	}
	for(int k=0; k<n; k++){
		int nd=arr[k].second;
		on[nd]=1;
		men[nd]=arr[k].first;
		sz[nd].push_back(nd);
		for(int i:adj[nd]){
			if(!on[i]) continue;
			if((int)men[find(i)]<arr[k].first){
				for(int j:sz[find(i)]) ans[j]=0;
				sz[find(i)].clear();
			}
			merge(i,nd);
		}
	}
	for(int i=0; i<n; i++) cout << ans[i];
}

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