Submission #953494

#	Time	Username	Problem	Language	Result	Execution time	Memory
953494		PM1	Stranded Far From Home (BOI22_island)	C++17	100 / 100	166 ms	41032 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=2e5+5;
ll n,m,par[mxn],s[mxn],root[mxn],sz[mxn],a[mxn];
vector<int>v[mxn],t,g[mxn];
bool ans[mxn];
bool cmp(int x,int y){
	return (s[x]!=s[y])?s[x]<s[y]:x<y;
}
int fndpar(int x){
	return (par[x]==x)?x:par[x]=fndpar(par[x]);
}
void dfs(int z){
	ans[z]=1;
	//cout<<z<<" ";
	for(auto i:g[z]){
		if(s[i]>=a[z])
			dfs(i);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=a[i];
		t.push_back(i);
		par[i]=i;
		root[i]=i;
		sz[i]=1;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(s[x]>s[y] || (s[x]==s[y] && y<x))
			v[x].push_back(y);
		else 
			v[y].push_back(x);
	}
	sort(t.begin(),t.end(),cmp);
	for(auto i:t){
		//cout<<i<<'\n';
		for(auto j:v[i]){
			int x=fndpar(j),y=fndpar(i);
			if(root[x]!=i){
				//cout<<root[x]<<" ";
				s[i]+=s[root[x]];
				g[i].push_back(root[x]);
				if(sz[x]>sz[y])swap(x,y);
				par[x]=y;
				sz[y]+=sz[x];
				root[y]=i;
			}
		}
		//cout<<'\n';
	}
	// /return 0;
	dfs(t.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