Submission #1221415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221415		Muhammad_Aneeq	Stranded Far From Home (BOI22_island)	C++17	100 / 100	209 ms	32428 KiB

island

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int const N=2e5+10;
vector<int>nei[N];
vector<int>ch[N]={};
int a[N]={},par[N]={},sz[N]={};
bool dead[N]={};
char ans[N]={};
int root(int n)
{
	return (par[n]==n?n:(par[n]=root(par[n])));
}
void merge(int a,int b)
{
	a=root(a);
	b=root(b);
	if (a==b)
		return;
	par[b]=a;
	ch[a].push_back(b);
	sz[a]+=sz[b];
}
void kill(int v)
{
	if (dead[v]) return;
	dead[v]=1;
	ans[v]='0';
	for (auto i:ch[v])
		kill(i);
}
inline void solve()
{
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>>vl;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		par[i]=i;
		sz[i]=a[i];
		ans[i]='1';
		vl.push_back({a[i],i});
	}
	sort(begin(vl),end(vl));
	for (int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	for (int i=0;i<n;i++)
	{
		int j=i;
		vector<int>cur;
		while (j<n&&vl[j].first==vl[i].first)
		{
			cur.push_back(vl[j].second);
			j++;
		}
		j--;
		int val=vl[i].first;
		i=j;
		for (auto i:cur)
		{
			for (auto j:nei[i])
			{
				if (a[j]<=val)
				{
					int u=root(i),v=root(j);
					if (u==v) continue;
					if (sz[v]<val)
						kill(v);
					merge(u,v);
				}
			}
		}
	}
	for (int i=1;i<=n;i++)
		cout<<ans[i];
	cout<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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