Submission #711014

#	Time	Username	Problem	Language	Result	Execution time	Memory
711014		ld_minh4354	Stranded Far From Home (BOI22_island)	C++17	100 / 100	368 ms	75516 KiB

island

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"

int n,m,s[200005],ans[200005];
pair<int,pair<int,int>> ed[200005];

int parent[200005],grpsize[200005],sum[200005];
set<int> nodes[200005];

int getroot(int x)
{
	if (x==parent[x]) return x;
	return getroot(parent[x]);
}

void merge(int x,int y,int id)
{
	int root_x=getroot(x);
	int root_y=getroot(y);
	
	if (root_x==root_y) return;
	
	if (sum[root_x]<ed[id].fi)
	{
		for (int u:nodes[root_x]) ans[u]=0;
		while (nodes[root_x].size()>0) nodes[root_x].erase(nodes[root_x].begin());
	}
	
	if (sum[root_y]<ed[id].fi)
	{
		for (int u:nodes[root_y]) ans[u]=0;
		while (nodes[root_y].size()>0) nodes[root_y].erase(nodes[root_y].begin());
	}
	
	if (grpsize[root_x]<grpsize[root_y]) swap(root_x,root_y);
	
	parent[root_y]=root_x;
	grpsize[root_x]+=grpsize[root_y];
	sum[root_x]+=sum[root_y];
	
	for (int u:nodes[root_y]) nodes[root_x].insert(u);
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int i,j;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>s[i];
	for (i=1;i<m+1;i++)
	{
		cin>>ed[i].se.fi>>ed[i].se.se;
		ed[i].fi=max(s[ed[i].se.fi], s[ed[i].se.se]);
	}
	
	sort(ed+1,ed+m+1);
	ed[m+1]={1e18,{0,0}};
	
	for (i=1;i<n+1;i++)
	{
		parent[i]=i;
		grpsize[i]=1;
		sum[i]=s[i];
		ans[i]=1;
		nodes[i].insert(i);
	}
	
	for (i=1;i<m+1;i++) merge(ed[i].se.fi, ed[i].se.se, i);

	for (j=1;j<n+1;j++) cout<<ans[j];
}

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