Submission #1217347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217347		MuhammadSaram	Stranded Far From Home (BOI22_island)	C++20	0 / 100	222 ms	47760 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 +1;

int a[M],col[M],sm[M];
vector<int> ver[M],pos[M];

void add(int u,int v)
{
	u=col[u],v=col[v];
	if (u==v) return;
	if (ver[u].size()<ver[v].size()) swap(u,v);
	for (int i:ver[v])
		col[i]=u,ver[u].push_back(i);
	for (int i:pos[v])
		pos[u].push_back(i);
	sm[u]+=sm[v];
	ver[v].clear();
	pos[v].clear();
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		cin>>a[i],col[i]=i,ver[i]=pos[i]={i},sm[i]=a[i];
	map<int,vector<pair<int,int>>> mp;
	for (int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		if (a[u]>a[v]) swap(u,v);
		mp[a[v]].push_back({u,v});
	}
	for (auto [i,edg]:mp)
	{
		for (auto [u,v]:edg)
			if (i>sm[col[u]])
				pos[col[u]].clear();
		for (auto [u,v]:edg)
			pos[col[u]].push_back(v),add(u,v);
	}
	string ans(n,'0');
	for (int i=1;i<=n;i++)
		if (col[i]==i)
			for (int u:pos[i])
				ans[u-1]='1';
	cout<<ans<<endl;
	
	return 0;
}

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