제출 #1217332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217332		Muhammad_Aneeq	Stranded Far From Home (BOI22_island)	C++20	10 / 100	119 ms	24240 KiB

island

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int const N=2e5+10;
vector<int>nei[N];
int a[N]={},par[N]={},sz[N]={};
bool dead[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;
	sz[a]+=sz[b];
}
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];
		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||dead[v]) continue;
					if (sz[v]<val)
					{
						dead[v]=1;
						sz[u]+=sz[v];
						continue;
					}
					merge(u,v);
				}
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		if (dead[root(i)])
			cout<<'0';
		else
			cout<<'1';
	}
	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: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35